제출 #945891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
945891		efedmrlr	Furniture (JOI20_furniture)	C++17	0 / 100	20 ms	1116 KiB

furniture

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 1e3+5;
const int ALPH = 26;
const int LGN = 25;
const int B = 5;
array<int, B> mods = {(int) 1e9 + 5, (int) 1e9 + 6, (int)1e9 + 7, (int) 1e9 + 8, (int) 1e9 + 9};
int n,m,q;

struct Fenwick {
    vector<vector<int> > data;
    int md;
    int sz1, sz2;
    void reset(int ms, int s1, int s2) {
        md = ms;
        sz1 = s1;
        sz2 = s2; 
        data.assign(s1 + 3, vector<int>(s2 + 3, 0));
    }
    void change(int x, int y, int val) {
        for(; x <= sz1; x += x & (-x)) {
            for(int i = y; i <= sz2; i += i & (-i)) {
                data[x][i] += val;
                data[x][i] %= md;
            }
        }
    }
    void upd(int x1, int y1, int x2, int y2, int val) {
        val %= md;
        int neg = md - val;
        change(x1, y1, val);
        change(x1, y2 + 1, neg);
        change(x2 + 1, y1, neg);
        change(x2 + 1, y2 + 1, val);
    }

    int getSum(int x, int y) {
        int ret = 0;
        for(; x > 0; x -= x & (-x)) {
            for(int i = y; i > 0; i -= i & (-i)) {
                ret += data[x][i];
                ret %= md;
            }   
        }
        return ret;
    }
};

Fenwick ft1[B], ft2[B];
inline void solve() {
    cin>>n>>m;
    REP(b,B) {
    ft1[b].reset(mods[b], n + 1, m + 1);
    ft2[b].reset(mods[b], n + 1, m + 1);
    }
    array<vector<vector<int> >, B> tmp;
    REP(b,B) {
        tmp[b].assign(n + 3, vector<int> (m + 3, 0));
        tmp[b][0][1] = 1;
    }
    vector<vector<bool> > gr(n + 3, vector<bool>(m + 3, 0));
    
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j <= m; j++) {
            bool f;
            cin >> f;
            gr[i][j] = f;
        }
    }
    REP(b,B) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(gr[i][j]) continue; 
                if(!gr[i - 1][j]) tmp[b][i][j] += tmp[b][i - 1][j];
                if(!gr[i][j - 1]) tmp[b][i][j] += tmp[b][i][j - 1];
                tmp[b][i][j] %= mods[b];
                ft1[b].upd(i, j, i, j, tmp[b][i][j]);
            }
        }
    }
    REP(b,B) {
        tmp[b].assign(n + 3, vector<int> (m + 3, 0));
        tmp[b][n][m + 1] = 1;
    }
    REP(b,B) {
        for(int i = n; i >= 1; i--) {
            for(int j = m; j >= 1; j--) {
                if(gr[i][j]) continue; 
                if(!gr[i + 1][j]) tmp[b][i][j] += tmp[b][i + 1][j];
                if(!gr[i][j + 1]) tmp[b][i][j] += tmp[b][i][j + 1];
                tmp[b][i][j] %= mods[b];
                ft2[b].upd(i, j, i, j, tmp[b][i][j]);
            }
        }
    }

    cin >> q;
    for(int i = 1; i<=q; i++) {
        int x,y;
        cin >> x >> y;
        bool f = 1;
        REP(b,B) {
            int res = 1ll * ft1[b].getSum(x, y) * ft2[b].getSum(x, y);
            res %= mods[b];
            if(res != ft1[b].getSum(n, m)) f = 0;
        }
        if(f) {
            cout << "0\n";
        }
        else {
            cout << "1\n";
            REP(b,B) {
                ft1[b].upd(x, y, n, m, mods[b] - ft1[b].getSum(x, y));
                ft2[b].upd(1, 1, x, y, mods[b] - ft2[b].getSum(x, y));
            }
        }
    }
}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95