oj.uz

답안 #993714

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
993714 2024-06-06T10:34:33 Z vyshniak_n Furniture (JOI20_furniture) C++17
100 / 100
 287 ms 21840 KB 
//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma traget("avx,avx2")

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

#include <random>
mt19937 rnd(time(0));

const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll maxn = 1e3 + 10;
const ll mod = 1e9 + 7;
const ll K = 7e6 + 100;
const ll LOG = 20;

ll a[maxn][maxn];
bool dpU[maxn][maxn];
bool dpD[maxn][maxn];
ll cnt[maxn + maxn];

void solve() {
    ll n, m;
    cin >> n >> m;

    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= m; j++)
            cin >> a[i][j], a[i][j] ^= 1;

    dpU[0][1] = 1;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= m; j++)
            dpU[i][j] = (dpU[i - 1][j] | dpU[i][j - 1]) & a[i][j];

    dpD[n + 1][m] = 1;
    for (ll i = n; i >= 1; i--)
        for (ll j = m; j >= 1; j--)
            dpD[i][j] = (dpD[i + 1][j] | dpD[i][j + 1]) & a[i][j];

    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= m; j++)
            if (dpU[i][j] && dpD[i][j])
                cnt[i + j]++;

    ll q;
    cin >> q;

    while (q--) {
        ll x, y;
        cin >> x >> y;

        if (cnt[x + y] == 1 && dpU[x][y] && dpD[x][y]) {
            cout << 0 << el;
            continue;
        }

        if (dpU[x][y] && dpD[x][y])
            cnt[x + y]--;

        cout << 1 << el;

        queue <point> line;
        line.push({x, y});

        dpU[x][y] = dpD[x][y] = 0;
        a[x][y] = 0;

        while (!line.empty()) {
            point v = line.front();
            line.pop();

            if (v.ff + 1 <= n) {
                point to = {v.ff + 1, v.ss};

                bool nw = (dpU[to.ff - 1][to.ss] | dpU[to.ff][to.ss - 1]) & a[to.ff][to.ss];
                if (nw != dpU[to.ff][to.ss]) {
                    if (dpU[to.ff][to.ss] && dpD[to.ff][to.ss])
                        cnt[to.ff + to.ss]--;
                    dpU[to.ff][to.ss] = nw;
                    line.push(to);
                }
            }
            if (v.ss + 1 <= m) {
                point to = {v.ff, v.ss + 1};

                bool nw = (dpU[to.ff - 1][to.ss] | dpU[to.ff][to.ss - 1]) & a[to.ff][to.ss];
                if (nw != dpU[to.ff][to.ss]) {
                    if (dpU[to.ff][to.ss] && dpD[to.ff][to.ss])
                        cnt[to.ff + to.ss]--;
                    dpU[to.ff][to.ss] = nw;
                    line.push(to);
                }
            }
        }

        line.push({x, y});
        while (!line.empty()) {
            point v = line.front();
            line.pop();

            if (v.ff - 1 >= 1) {
                point to = {v.ff - 1, v.ss};

                bool nw = (dpD[to.ff + 1][to.ss] | dpD[to.ff][to.ss + 1]) & a[to.ff][to.ss];
                if (nw != dpD[to.ff][to.ss]) {
                    if (dpU[to.ff][to.ss] && dpD[to.ff][to.ss])
                        cnt[to.ff + to.ss]--;
                    dpD[to.ff][to.ss] = nw;
                    line.push(to);
                }
            }
            if (v.ss - 1 >= 1) {
                point to = {v.ff, v.ss - 1};
                bool nw = (dpD[to.ff + 1][to.ss] | dpD[to.ff][to.ss + 1]) & a[to.ff][to.ss];
                if (nw != dpD[to.ff][to.ss]) {
                    if (dpU[to.ff][to.ss] && dpD[to.ff][to.ss])
                        cnt[to.ff + to.ss]--;
                    dpD[to.ff][to.ss] = nw;
                    line.push(to);
                }
            }
        }
    }
    return;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tests = 1;
    //cin >> tests;

    while (tests--) 
        solve();
    return 0;
}
/*
*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4644 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 3 ms 4712 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4644 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 3 ms 4712 KB Output is correct
10 Correct 9 ms 4956 KB Output is correct
11 Correct 3 ms 4444 KB Output is correct
12 Correct 124 ms 14728 KB Output is correct
13 Correct 43 ms 11612 KB Output is correct
14 Correct 268 ms 19276 KB Output is correct
15 Correct 287 ms 19516 KB Output is correct
16 Correct 272 ms 20560 KB Output is correct
17 Correct 276 ms 21328 KB Output is correct
18 Correct 280 ms 20764 KB Output is correct
19 Correct 255 ms 21832 KB Output is correct
20 Correct 250 ms 21704 KB Output is correct
21 Correct 260 ms 21840 KB Output is correct