QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#656583 | #7926. Color Inversion on a Huge Chessboard | gambit# | WA | 1ms | 11528kb | C++17 | 1.7kb | 2024-10-19 13:22:22 | 2024-10-19 13:22:24 |
Judging History
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'