Zadanie Tablica Binarna OI - optymalizacja rozwiązania

Question

Męczę się z takim zadaniem z OI-a: https://szkopul.edu.pl/problemset/problem/3sQlWSD2omwi4M_wdqCbycIW/site/?key=statement

Wymyśliłem rozwiązanie w O(n*m*q) - przechodzi na 60pkt. Mianowicie:

Jesli mamy sprawdzić jakąś tablicę binarną (w ile ruchów da się doprowadzić do zer), to zauważyłem, że musimy iść od największych m(j), i dla każdego j iść w kolejności od n do 1. W sensie:

for (int j = m; j >= 1; --j)
{
    for (int i = n; i >= 1; --i)
    {
         
    }
}

I teraz, jeśli plansza[i][j] jest  jedynką, to obracamy na prostokącie 1,1 do i,j. I zeby nie mieć O(n^2*m^2*g) btw. to wchodzi na 39pkt, to naliczam sobie dp. dp[i][j] / sumy prefiksowe -> ile liczb obrucimy w prostokącie i,j do n,m. Tylko jest problem, bo dla każdego zapytania naliczam to dp, i nie wiem jak podejśc do tego sprytniej, żeby nie musieć naliczać cały czas.

Ma ktoś jakiś pomysł?

Kod:

#include <iostream>
#include <vector>

using namespace std;

int n = 0, m = 0, q = 0, y_1 = 0, x_1 = 0, y_2 = 0, x_2 = 0, wyn = 0;
vector<vector<bool>> plansza;
vector<vector<int>> dp;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> q;
    for (int i = 0; i <= n; ++i)
    {
        plansza.push_back({});
        dp.push_back({});
        for (int j = 0; j <= m; ++j)
        {
            plansza[i].push_back(false);
            dp[i].push_back(0);
        }
    }
    while(q--)
    {
        cin >> y_1 >> x_1 >> y_2 >> x_2;
        y_1--;
        x_1--;
        y_2--;
        x_2--;
        wyn = 0;

        for (int i = y_1; i <= y_2; ++i)
            for (int j = x_1; j <= x_2; ++j)
                plansza[i][j] = !plansza[i][j];

        for (int i = 0; i <= n; ++i)
        {
            for (int j = 0; j <= m; ++j)
            {
                if (plansza[i][j] == true)
                    dp[i][j] = 1;
                else
                    dp[i][j] = 0;
            }
        }

        for (int j = m-1; j >= 0; --j)
        {
            for (int i = n-1; i >= 0; --i)
            {
                dp[i][j] += dp[i+1][j] + dp[i][j+1] - dp[i+1][j+1];
                if (dp[i][j] % 2 == 1)
                {
                    dp[i][j] = dp[i+1][j] + dp[i][j+1] - dp[i+1][j+1] + 1;
                    if (dp[i][j] % 1 == 0)
                        wyn++;
                }
                else
                    dp[i][j] = dp[i+1][j] + dp[i][j+1] - dp[i+1][j+1];
            }
        }
        printf("%d\n",wyn);
    }
    return 0;
}

 

Comments

Robiłem kiedyś to zadanie, ale nie pamiętam jaka była idea wzorcówki. Mogę natomiast dać kod

---

Poproszę

---

#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

typedef uint32_t ul;
typedef int32_t l;
typedef uint64_t ull;
typedef int64_t ll;

const l INF = 1000000000 + 9;
const ll MOD = 123456789;
const l PRIME = 200003;
const ll L_INF = 1000000000000000000LL + 7;
const double EPS = 1e-5;

#define FOR(x, y, z) for (l z = x; z < y; z++)
#define FORE(x, y, z) for (l z = x; z <= y; z++)
#define FORD(x, y, z) for (l z = x; z > y; z--)
#define FORDE(x, y, z) for (l z = x; z >= y; z--)
#define REP(x, y) for (l y = 0; y < x; y++)
#define ALL(...) (__VA_ARGS__).begin(), (__VA_ARGS__).end()

#define PF push_front
#define POF pop_front
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FS first
#define SC second

const l MAXN = 1005;

l n, m, q, res;
l tab[MAXN][MAXN];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> q;

    l a, b, c, d;
    REP(q, k)
    {
        cin >> a >> c >> b >> d;

        res += 1 - 2*tab[b][d];
        tab[b][d] ^= 1;

        if(a-1 > 0)
        {
            res += 1 - 2*tab[a-1][d];
            tab[a-1][d] ^= 1;

            if(c-1 > 0)
            {
                res += 1 - 2*tab[a-1][c-1];
                tab[a-1][c-1] ^= 1;
            }
        }

        if(c-1 > 0)
        {
            res += 1 - 2*tab[b][c-1];
            tab[b][c-1] ^= 1;
        }

        cout << res << '\n';
    }
}

 

---

A pisanie:

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

A tak jak ty piszesz

ios_base::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);

Ma jakieś znaczenie, czy to tosamo?

---

To samo. *.tie przyjmuje wskaźnik, ale można dać też 0. Tu jest wytłumaczenie dlaczego tak można