QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #83367 | #2831. Game Theory | uniecho1# | TL | 0ms | 7420kb | C++14 | 3.0kb | 2023-03-01 16:58:49 | 2023-03-01 16:58:52 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define mkp make_pair
using namespace std;
const int MAXN = 2e5 + 5;
const int mod = 998244353;
struct segtree {
int sum[MAXN << 2], num[MAXN << 2];
bool rev[MAXN << 2];
void update(int id) {
sum[id] = (sum[id << 1] + sum[id << 1 | 1]) % mod;
num[id] = num[id << 1] + num[id << 1 | 1];
}
void pushdown(int l, int r, int id) {
if (rev[id]) {
rev[id] ^= 1;
rev[id << 1] ^= 1;
rev[id << 1 | 1] ^= 1;
int m = l + r >> 1;
sum[id << 1] = ((l + m) * (m - l + 1) / 2 - sum[id << 1]) % mod;
num[id << 1] = (m - l + 1) - num[id << 1];
sum[id << 1 | 1] =
((m + 1 + r) * (r - m) / 2 - sum[id << 1 | 1]) % mod;
num[id << 1 | 1] = (r - m) - num[id << 1 | 1];
}
}
void build(int l, int r, int id) {
rev[id] = 0;
sum[id] = num[id] = 0;
if (l == r) {
char c;
cin >> c;
if (c == '1') num[id] = 1, sum[id] = l;
return;
}
int m = l + r >> 1;
build(l, m, id << 1);
build(m + 1, r, id << 1 | 1);
update(id);
}
void revolve(int x, int y, int l, int r, int id) {
// cout << l << " " << r << endl;
if (x > y) return;
if (x <= l && r <= y) {
sum[id] = ((l + r) * (r - l + 1) / 2 - sum[id]) % mod;
num[id] = r - l + 1 - num[id];
rev[id] = true;
return;
}
pushdown(l, r, id);
int m = l + r >> 1;
if (x <= m) revolve(x, y, l, m, id << 1);
if (y > m) revolve(x, y, m + 1, r, id << 1 | 1);
update(id);
}
pii query(int x, int y, int l, int r, int id) {
// cout << x << " " << y << " " << l << " " << r << endl;
if (x > y) return mkp(0, 0);
if (x <= l && r <= y) return mkp(sum[id], num[id]);
int m = l + r >> 1;
pushdown(l, r, id);
if (x <= m && y > m) {
auto a = query(x, y, l, m, id << 1);
auto b = query(x, y, m + 1, r, id << 1 | 1);
return mkp((a.first + b.first) % mod, a.second + b.second);
} else if (x <= m)
return query(x, y, l, m, id << 1);
else
return query(x, y, m + 1, r, id << 1 | 1);
}
} T;
int N, Q;
signed main() {
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
while (cin >> N >> Q) {
T.build(1, N, 1);
for (int i = 1, l, r; i <= Q; i++) {
cin >> l >> r;
T.revolve(l, r, 1, N, 1);
int k = T.query(1, N, 1, N, 1).second;
int part2 = T.query(k + 1, N, 1, N, 1).first;
int part1 = T.query(1, k, 1, N, 1).first;
part1 = ((1 + k) * k / 2 - part1) % mod;
int ans = (k - 2 * part1 % mod + 2 * part2 % mod + mod) % mod;
cout << ans << endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7404kb
input:
3 2 010 1 2 2 3 5 1 00000 1 5
output:
1 3 5
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 7420kb
input:
1 1 0 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Time Limit Exceeded
input:
2 2 01 2 2 2 2 2 2 01 1 2 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 2 2 00 1 2 1 2 2 2 11 1 2 1 2 2 2 01 2 2 1 1 2 2 10 2 2 1 2 2 2 01 1 2 1 2 1 2 0 1 1 1 1 2 2 01 1 2 2 2 1 2 0 1 1 1 1 1 2 1 1 1 1 1 2 2 10 1 2 1 1 1 2 0 1 1 1 1 2 2 01 1 2 1 2 2 2 10 1 2 1 1 1 2 0 1 1 1 1 1 2 0 1 1 1 1 1 2 1 1 1 1 1 2 2 10 1 ...
output:
0 3 1 3 0 1 0 1 2 0 0 2 0 1 2 0 1 3 1 0 1 2 1 0 0 1 3 2 1 0 1 3 3 2 1 0 1 0 0 1 0 1 0 2 2 1 0 1 2 1 1 0 2 0 2 3 1 0 0 1 2 0 0 1 0 1 0 1 1 0 1 2 2 0 0 2 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 2 0 3 0 1 0 0 1 1 0 1 0 1 2 0 2 1 0 0 3 1 2 0 1 3 2 1 0 0 1 2 0 2 0 0 1 0 1 1 0 1 0 1 0 1 0 1 2 1 0 3 1 0 3 0 1 0 1 ...