QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#83370	#2831. Game Theory	uniecho1^#	TL	0ms	7592kb	C++14	3.1kb	2023-03-01 17:00:21	2023-03-01 17:01:32

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-01 17:01:32]
评测

测评结果：TL
用时：0ms
内存：7592kb

查看

[2023-03-01 17:00:21]
提交

answer

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define mkp make_pair
#define endl '\n'
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;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 5484kb

input:

output:

1
3
5

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 7592kb

input:

1 1
0
1 1

output:

result:

ok single line: '1'

Test #3:

score: -100

Time Limit Exceeded

input:

output: