oj.uz

Submission #945843

# Submission time Handle Problem Language Result Execution time Memory
945843 2024-03-14T08:08:50 Z efedmrlr Furniture (JOI20_furniture) C++17
0 / 100
 3 ms 348 KB 
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli 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 = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+9;
int n,m,q;

struct Fenwick {
    vector<vector<int> > data;
    int sz1, sz2;
    void reset(int s1, int s2) {
        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] %= MOD;
            }
        }
    }
    void upd(int x1, int y1, int x2, int y2, int val) {
        val %= MOD;
        int neg = MOD - 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 %= MOD;
            }   
        }
        return ret;
    }
};

Fenwick ft1, ft2;
inline void solve() {
    cin>>n>>m;
    ft1.reset(n + 1, m + 1);
    ft2.reset(n + 1, m + 1);
    vector<vector<int> > tmp(n + 1, vector<int>(m + 1, 0));
    vector<vector<bool> > gr(n + 3, vector<bool>(m + 3, 0));
    tmp[0][1] = 1;
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j <= m; j++) {
            bool f;
            cin >> f;
            gr[i][j] = f;
        }
    }
    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[i][j] += tmp[i - 1][j];
            if(!gr[i][j - 1]) tmp[i][j] += tmp[i][j - 1];
            tmp[i][j] %= MOD;
            ft1.upd(i, j, i, j, tmp[i][j]);
        }
    }
    tmp.assign(n + 3, vector<int>(m + 3, 0));
    tmp[n][m + 1] = 1;
    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[i][j] += tmp[i + 1][j];
            if(!gr[i][j + 1]) tmp[i][j] += tmp[i][j + 1];
            tmp[i][j] %= MOD;
            ft2.upd(i, j, i, j, tmp[i][j]);
        }
    }

    cin >> q;
    for(int i = 1; i<=q; i++) {
        int x,y;
        cin >> x >> y;
        lli res = 1ll * ft1.getSum(x, y) * ft2.getSum(x, y);
        res %= MOD;
        if(res == (lli)ft1.getSum(n, m)) {
            cout << "0\n";
        }
        else {
            cout << "1\n";
            ft1.upd(x, y, n, m, MOD - ft1.getSum(x, y));
            ft2.upd(1, 1, x, y, MOD - ft2.getSum(x, y));
        }
    }
}
 
signed main() {

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

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Incorrect 3 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Incorrect 3 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -