QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#762274#5441. Quartz CollectionSGColin#WA 3ms35620kbC++142.7kb2024-11-19 14:23:422024-11-19 14:23:46

Judging History

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

  • [2024-11-19 14:23:46]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:35620kb
  • [2024-11-19 14:23:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;

#define eb emplace_back
#define pb push_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

constexpr int N = 100007;

struct node {
    ll sum[4];
    int cnt;
    node(){cnt = 0; memset(sum, 0, sizeof(sum));};
    node operator + (const node &obj) const {
        node ret;
        ret.cnt = cnt + obj.cnt;
        rep(i, 0, 3) ret.sum[i] = sum[i];
        rep(i, 0, 3) ret.sum[(i + cnt) % 4] += obj.sum[i];
        return ret;
    }
};

struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)
    node c[N << 2];
    void upd(int rt, int l, int r, int pos, bool w) {
        if (l == r) {
            if (w) {
                c[rt].cnt++;
                c[rt].sum[c[rt].cnt % 4] += pos;
            } else {
                c[rt].sum[c[rt].cnt % 4] -= pos;
                c[rt].cnt--;
            }
            return;
        }
        pos <= mid ? upd(ls, l, mid, pos, w) : upd(rs, mid + 1, r, pos, w);
        c[rt] = c[ls] + c[rs];
    }
} t1, t2;

int a[N], b[N];

ll sumb = 0;

int main() {
    int n = rd(), q = rd();
    rep(i, 1, n) {
        a[i] = rd(); b[i] = rd(); sumb += b[i];
        if (a[i] > b[i]) t2.upd(1, 1, 100000, a[i] - b[i], 1);
        else t1.upd(1, 1, 100000, b[i] - a[i], 1);
    }
    auto calc = [&]() {
        node A = t1.c[1], B = t2.c[1];
        //printf("%d %lld %lld %lld %lld\n", A.cnt, A.sum[0], A.sum[1], A.sum[2], A.sum[3]);
       // printf("%d %lld %lld %lld %lld\n", B.cnt, B.sum[0], B.sum[1], B.sum[2], B.sum[3]);
        int cnt = A.cnt;
        ll ans = sumb;
        ans -= A.sum[cnt % 4];
        ans -= A.sum[(cnt + 1) % 4];
        //printf("%lld\n", ans);
        ans += B.sum[(cnt + 1) % 2];
        ans += B.sum[(cnt + 1) % 2 + 2];
        return ans;
    };
    printf("%lld\n", calc());
    rep(t, 1, q) {
        int i = rd();
        if (a[i] > b[i]) t2.upd(1, 1, 100000, a[i] - b[i], 0);
        else t1.upd(1, 1, 100000, b[i] - a[i], 0);
        sumb -= b[i];
        a[i] = rd(); b[i] = rd(); sumb += b[i];
        if (a[i] > b[i]) t2.upd(1, 1, 100000, a[i] - b[i], 1);
        else t1.upd(1, 1, 100000, b[i] - a[i], 1);
        printf("%lld\n", calc());
    }
    return 0;
}

详细

Test #1:

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

input:

4 5
2 4
5 7
1 7
2 1
4 5 2
1 6 2
4 4 3
2 1 3
3 6 6

output:

13
14
15
14
10
13

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 3ms
memory: 35180kb

input:

1 1
1 1
1 1 1

output:

1
1

result:

ok 2 number(s): "1 1"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 35620kb

input:

100 100
6 7
100 8
5 61
5 75
59 65
51 47
83 37
34 54
87 46
4 26
21 87
12 97
86 68
60 11
62 76
14 83
29 31
91 62
57 80
47 75
85 97
62 77
91 86
14 25
48 77
83 65
39 61
78 77
45 46
90 74
100 91
86 98
55 5
84 42
91 69
100 4
74 98
60 37
75 44
41 12
15 34
36 1
99 16
7 87
36 26
79 42
41 84
17 98
72 16
38 55...

output:

5109
5066
5061
5007
4975
4993
4950
4927
4922
4929
4948
4915
4885
4863
4897
4863
4837
4787
4793
4775
4730
4709
4660
4617
4546
4618
4655
4687
4677
4685
4714
4732
4728
4700
4659
4630
4627
4681
4742
4776
4764
4772
4754
4760
4715
4743
4671
4686
4700
4649
4611
4542
4523
4555
4605
4585
4532
4519
4488
4505
...

result:

wrong answer 2nd numbers differ - expected: '5065', found: '5066'