QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#656583#7926. Color Inversion on a Huge Chessboardgambit#WA 1ms11528kbC++171.7kb2024-10-19 13:22:222024-10-19 13:22:24

Judging History

你现在查看的是最新测评结果

  • [2024-10-19 13:22:24]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:11528kb
  • [2024-10-19 13:22:22]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class segtree {
    vector<ll> seg; int n, sz; ll id = 0;
public:
    segtree(int n) {
        this->n = n;
        this->sz = 1 << ((int)log2(n - 0.5) + 1);
        seg.resize(sz << 1);
        for (int i = 0; i < sz; i++) seg[i + sz] = id;
    }
    ll op(ll a, ll b) {
        return a + b;
    }
    void init() {
        for (int i = sz - 1; i > 0; i--) {
            seg[i] = op(seg[i << 1], seg[i << 1 | 1]);
        }
    }
    void update(int idx, ll val) {
        seg[sz + idx] = val;
        for (int i = (sz + idx) >> 1; i > 0; i >>= 1) {
            seg[i] = op(seg[i << 1], seg[i << 1 | 1]);
        }
    }
    ll query(int left, int right) {
        ll ret = id;
        for (int l = left + sz, r = right + sz; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) ret = op(ret, seg[l++]);
            if (~r & 1) ret = op(ret, seg[r--]);
        }
        return ret;
    }
    ll& operator[] (const int& idx) {
        return seg[sz + idx];
    }
};
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q; segtree r(n), c(n);
    for (int i = 0; i < n; i++) r[i] = 1, c[i] = 1;
    r.init(); c.init();
    while (q--) {
        string op; int x; cin >> op >> x; x--;
        if (op == "ROW") {
            if (x > 0) r.update(x - 1, 1 - r[x - 1]);
            if (x < n - 1) r.update(x + 1, 1 - r[x + 1]);
        } else {
            if (x > 0) c.update(x - 1, 1 - c[x - 1]);
            if (x < n - 1) c.update(x + 1, 1 - c[x + 1]);
        }
        cout << r.query(0, n - 1) * c.query(0, n - 1) << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3632kb

input:

3 3
ROW 2
COLUMN 3
ROW 2

output:

3
2
6

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 11528kb

input:

200000 2
ROW 1
ROW 1

output:

39999800000
40000000000

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

1 1
COLUMN 1

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

1 100
COLUMN 1
COLUMN 1
ROW 1
ROW 1
COLUMN 1
ROW 1
COLUMN 1
COLUMN 1
ROW 1
ROW 1
COLUMN 1
COLUMN 1
ROW 1
COLUMN 1
COLUMN 1
COLUMN 1
ROW 1
COLUMN 1
ROW 1
COLUMN 1
COLUMN 1
ROW 1
COLUMN 1
COLUMN 1
ROW 1
COLUMN 1
COLUMN 1
ROW 1
COLUMN 1
COLUMN 1
ROW 1
COLUMN 1
COLUMN 1
ROW 1
COLUMN 1
ROW 1
COLUMN 1
COL...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 100 lines

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3652kb

input:

2 100
COLUMN 2
ROW 1
COLUMN 2
COLUMN 2
ROW 2
ROW 1
COLUMN 1
COLUMN 1
COLUMN 1
ROW 1
ROW 1
ROW 1
COLUMN 1
ROW 2
COLUMN 1
COLUMN 2
COLUMN 1
ROW 1
ROW 2
ROW 1
COLUMN 2
ROW 2
ROW 2
COLUMN 2
COLUMN 1
ROW 2
COLUMN 2
ROW 1
ROW 2
ROW 1
ROW 1
COLUMN 2
COLUMN 2
COLUMN 2
COLUMN 2
ROW 2
ROW 1
ROW 1
COLUMN 1
ROW...

output:

2
1
2
1
0
1
0
1
0
0
0
0
0
1
0
1
2
4
2
0
0
1
0
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
2
1
0
1
2
1
2
0
2
4
2
4
2
4
2
4
2
1
0
1
0
1
2
0
2
1
2
4
2
4
2
1
2
1
0
0
0
1
2
0
2
1
2
4
2
1
2
0
0
0
0
1
2
4
2
1
0
0
0
0
2
4

result:

wrong answer 5th lines differ - expected: '2', found: '0'