QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#297365#6630. Triangle CollectionA_programmer0 34ms5872kbC++171.9kb2024-01-04 12:30:112024-01-04 12:30:12

Judging History

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

  • [2024-01-04 12:30:12]
  • 评测
  • 测评结果:0
  • 用时:34ms
  • 内存:5872kb
  • [2024-01-04 12:30:11]
  • 提交

answer

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

typedef long long ll;
const int maxn = 2e5 + 5;

int n;
ll c[maxn], pre[maxn], pre2[maxn], pre3[maxn], suf[maxn];

#define ls k << 1
#define rs k << 1 | 1

struct segtree
{
	struct segnode
	{
		int l, r;
		ll mx, lz;
	}t[maxn << 2];
	
	inline void pushup(int k) { t[k].mx = max(t[ls].mx, t[rs].mx); }
	inline void upd(int k, ll d) { t[k].mx += d; t[k].lz += d; }
	inline void pushdown(int k)
	{
		if (t[k].lz)
		{
			upd(ls, t[k].lz);
			upd(rs, t[k].lz);
			t[k].lz = 0;
		}
	}
	
	void build(int k, int l, int r)
	{
		t[k].l = l, t[k].r = r;
		if (l == r)
		{
			t[k].mx = pre[l] - pre2[min(n, 2 * l - 1)];
			return;
		}
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
		pushup(k);
	}
	
	void update(int k, int l, int r, ll d)
	{
		if (l <= t[k].l && t[k].r <= r)
		{
			upd(k, d);
			return;
		}
		pushdown(k);
		int mid = (t[k].l + t[k].r) >> 1;
		if (l <= mid) update(ls, l, r, d);
		if (r > mid) update(rs, l, r, d);
		pushup(k);
	}
	
	ll query(int k, int l, int r)
	{
		if (l <= t[k].l && t[k].r <= r) return t[k].mx;
		pushdown(k);
		int mid = (t[k].l + t[k].r) >> 1; ll ans = 0;
		if (l <= mid) ans = max(ans, query(ls, l, r));
		if (r > mid) ans = max(ans, query(rs, l, r));
		return ans;
	}
}T;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); 
	
	int q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
	{
		cin >> c[i];
		pre[i] = pre[i - 1] + c[i] / 2;
		pre2[i] = pre2[i - 1] + (c[i] & 1);
	}
	T.build(1, 1, n);
	
	
	ll sum = pre[n];
	while (q--)
	{
		int x, d;
		cin >> x >> d;
		sum -= c[x] / 2;
		T.update(1, x, n, -c[x] / 2);
		T.update(1, (x + 1) / 2, n, (c[x] & 1));
		c[x] += d;
		sum += c[x] / 2;
		T.update(1, x, n, c[x] / 2);
		T.update(1, (x + 1) / 2, n, -(c[x] & 1));
		cout << sum - (T.t[1].mx + 2) / 3 << "\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 0ms
memory: 3596kb

input:

1 23
1485
1 -12
1 -30
1 -20
1 6
1 24
1 5
1 31
1 14
1 -34
1 -22
1 -45
1 37
1 46
1 9
1 22
1 -9
1 9
1 -46
1 -47
1 39
1 36
1 -36
1 50

output:

491
481
474
476
484
486
496
501
489
482
467
479
495
498
505
502
505
490
474
487
499
487
504

result:

ok 23 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 5608kb

input:

12 1
13 79 59 21 32 13 85 40 74 15 49 56
3 31

output:

189

result:

ok 1 number(s): "189"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

50 1995
3 2 3 0 3 0 5 2 2 2 3 0 4 5 4 4 3 0 1 0 5 5 3 4 3 3 1 1 4 5 5 4 1 1 3 1 4 2 1 3 4 1 5 5 0 3 0 3 4 3
49 1
48 -2
45 3
49 0
31 -4
13 0
15 -2
48 0
38 -2
8 0
48 3
12 1
22 -4
7 -5
5 -1
3 1
15 -2
37 -4
39 -1
24 -2
11 2
35 -2
17 -1
41 -2
20 5
8 0
18 0
26 -3
25 -3
49 -5
31 4
46 -2
38 0
42 3
16 -4
5 3...

output:

44
44
45
45
43
43
43
43
42
42
43
43
42
40
40
40
40
38
38
37
38
37
37
36
38
38
38
37
36
34
36
35
35
36
35
36
36
37
36
37
37
38
38
38
39
38
37
36
36
35
36
36
36
36
35
35
35
35
33
35
35
34
34
33
34
35
36
36
35
35
37
36
36
36
35
35
35
35
35
36
37
37
37
36
37
36
38
38
38
39
39
38
38
38
37
39
39
41
40
40
...

result:

ok 1995 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 5596kb

input:

50 1996
0 1 0 1 2 2 4 1 3 2 5 3 4 1 5 5 1 2 0 2 1 2 5 4 3 1 4 5 1 2 3 5 5 1 4 4 2 3 5 3 1 3 2 3 3 0 4 2 5 0
29 4
50 3
30 2
6 0
26 -1
13 -2
34 1
5 2
23 -5
45 1
30 -4
17 3
40 1
49 -5
24 -1
35 -2
12 -2
30 1
3 0
5 -3
38 0
14 -1
38 2
25 -3
25 0
26 2
20 1
24 2
43 1
27 -2
38 -2
12 3
43 1
4 3
13 1
25 2
26 -...

output:

44
45
46
46
46
45
45
46
44
45
43
44
45
43
43
42
41
42
42
41
41
40
41
40
40
41
41
42
42
41
41
42
42
43
43
44
44
44
44
45
45
46
47
47
47
46
46
44
44
44
44
44
44
44
43
43
42
41
41
42
43
43
45
45
45
45
45
45
45
44
43
44
44
44
45
44
45
46
45
44
43
43
43
43
43
44
44
44
46
45
43
44
44
44
43
44
45
44
44
44
...

result:

ok 1996 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 5764kb

input:

50 1997
39 35 37 37 36 36 38 37 36 36 37 40 37 39 40 37 38 35 36 36 37 36 40 36 40 37 40 37 37 38 39 35 40 36 38 40 35 36 39 38 38 37 35 37 36 37 36 36 36 37
3 0
13 3
33 -3
24 2
25 0
9 3
18 2
11 0
28 2
39 -2
9 -2
5 -1
2 0
25 -3
25 3
47 1
10 4
34 2
8 -1
32 0
47 -2
17 -2
20 0
3 3
39 3
1 -4
18 2
35 0
3...

output:

620
621
620
621
621
622
622
622
623
622
622
621
621
620
621
622
623
624
623
623
623
622
622
623
624
623
623
623
622
622
623
623
624
624
624
625
624
623
622
621
620
619
618
617
615
616
617
617
618
616
616
617
616
616
616
617
619
618
617
617
617
618
619
618
619
618
619
620
619
619
620
621
620
620
621
...

result:

ok 1997 numbers

Test #6:

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

input:

2000 2000
2 1 2 1 4 1 5 1 0 0 1 2 0 2 2 0 2 1 0 0 1 0 1 1 1 0 4 1 0 0 5 2 1 0 1 6 0 0 1 1 1 0 0 0 0 1 1 0 0 2 0 0 1 1 0 1 1 1 0 0 1 0 3 0 0 0 2 1 0 1 2 0 0 3 2 1 0 0 0 0 1 1 0 1 2 0 0 0 0 0 2 3 0 2 0 4 0 1 2 0 0 0 1 0 1 5 0 0 0 4 0 0 1 2 3 0 1 0 1 0 1 0 2 0 1 0 1 2 1 1 2 1 0 2 0 0 0 2 3 6 1 0 0 0 1 ...

output:

649
649
649
649
649
649
649
649
648
648
649
649
649
649
649
649
649
650
650
650
650
650
650
650
650
649
650
650
649
650
650
650
650
650
650
650
650
649
649
649
649
648
650
650
650
650
650
650
649
649
649
649
650
650
650
650
650
650
650
650
650
651
651
651
651
651
651
651
651
651
651
651
650
652
652
...

result:

ok 2000 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 5720kb

input:

2000 2000
0 1 3 1 1 4 0 0 1 0 1 0 0 0 1 0 0 1 0 2 1 0 0 4 0 0 1 0 0 2 0 0 0 0 1 0 2 1 0 1 0 2 0 5 0 0 1 0 2 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 4 3 0 0 1 1 0 0 3 0 0 0 0 1 8 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 2 0 0 0 0 3 2 0 1 1 4 2 4 2 2 0 3 0 1 0 0 3 0 3 0 0 0 5 1 0 0 0 0 2 1 1 0 1 1 1 0 0 5 2 4 0 0 0 1 0 ...

output:

666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
665
664
666
666
666
666
666
666
666
666
665
665
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
665
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
...

result:

ok 2000 numbers

Test #8:

score: 0
Accepted
time: 2ms
memory: 5832kb

input:

1000 2000
2 8 1 1 4 1 1 1 2 1 1 2 1 2 1 3 1 1 3 2 1 2 2 1 2 2 2 3 5 1 1 2 1 5 4 1 1 1 2 1 1 1 1 2 2 1 1 2 1 1 2 2 4 2 1 4 2 1 1 2 5 1 4 2 3 1 4 4 1 1 2 1 1 2 2 1 1 1 2 1 1 2 3 2 1 1 2 1 1 1 1 1 1 1 1 3 1 2 1 2 1 1 1 1 2 1 4 3 2 1 3 1 6 4 1 2 2 3 1 2 5 1 1 3 3 2 2 1 2 1 1 2 3 6 1 1 3 2 2 1 2 3 1 2 1 ...

output:

660
660
660
660
659
659
658
659
659
659
659
659
659
659
660
660
660
659
658
658
659
659
659
659
657
658
659
659
658
657
656
657
658
658
658
657
656
656
657
657
657
657
657
657
656
657
656
655
656
656
656
657
657
657
655
655
656
656
657
657
657
657
657
657
656
657
655
653
655
654
655
656
655
654
655
...

result:

ok 2000 numbers

Test #9:

score: 0
Accepted
time: 2ms
memory: 5872kb

input:

2000 2000
1 2 0 2 2 0 2 0 2 0 1 1 1 0 1 1 1 1 1 2 0 1 0 2 0 1 2 1 1 2 0 2 2 1 1 0 0 2 0 1 1 1 2 2 2 2 2 0 2 2 1 0 1 2 2 0 1 2 2 2 0 0 0 1 0 0 1 1 1 1 1 1 1 2 0 0 0 0 2 1 1 1 2 0 1 2 1 2 0 1 0 2 2 1 2 1 0 2 2 1 0 0 0 2 0 1 0 1 1 1 0 0 1 0 0 2 2 2 0 2 2 0 0 1 2 2 0 1 0 1 1 1 1 1 0 2 2 1 1 0 1 0 1 2 1 ...

output:

652
652
652
652
652
652
653
653
653
653
653
653
653
653
654
655
655
655
654
655
654
653
653
654
653
654
655
654
654
653
653
652
653
654
654
655
656
656
655
654
654
654
655
655
655
656
657
657
657
657
657
657
658
659
659
660
661
660
661
660
660
660
659
659
658
657
656
657
657
657
656
656
656
656
657
...

result:

ok 2000 numbers

Test #10:

score: -5
Wrong Answer
time: 2ms
memory: 5824kb

input:

2000 2000
0 3 0 0 2 1 0 0 0 0 1 0 1 0 5 0 0 0 2 5 2 0 0 3 1 0 3 2 0 0 3 0 1 0 4 0 1 0 0 2 2 0 0 0 3 0 0 0 0 2 3 1 0 1 1 0 7 3 1 1 2 0 0 0 0 0 2 0 1 0 0 0 1 0 0 1 2 0 2 1 1 0 2 0 0 0 1 0 0 0 0 0 1 0 0 2 0 0 0 0 1 1 1 1 1 0 0 2 0 5 2 0 1 0 5 1 2 3 2 1 0 0 0 1 1 0 0 0 1 2 1 0 1 1 0 0 0 0 2 0 3 0 1 2 0 ...

output:

666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
665
665
664
665
665
665
664
664
664
664
664
663
664
663
663
662
662
662
662
662
662
662
662
662
662
662
662
661
661
661
661
661
661
660
660
660
660
660
661
661
661
661
661
661
662
662
662
661
660
660
...

result:

wrong answer 1125th numbers differ - expected: '624', found: '623'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #28:

score: 5
Accepted
time: 2ms
memory: 3764kb

input:

1999 2000
1 1 1 1 0 2 0 2 1 0 2 1 2 2 2 1 2 0 0 1 2 2 0 1 0 1 0 2 0 0 2 1 1 1 1 0 1 2 1 2 1 1 1 1 1 0 2 2 0 2 1 1 2 0 0 2 0 0 2 1 2 0 0 1 1 2 0 2 2 2 1 2 0 2 1 2 0 1 2 2 2 1 1 2 1 1 1 1 0 0 1 1 0 1 2 1 0 0 2 0 2 2 2 0 1 1 2 0 0 1 0 0 2 1 2 1 2 0 1 1 2 2 0 0 1 2 2 1 2 1 2 2 2 0 0 1 1 2 1 1 2 2 2 2 2 ...

output:

660
660
660
661
661
661
661
660
660
660
660
661
662
662
663
663
662
661
662
662
661
660
661
660
660
660
661
661
661
661
662
661
661
660
661
660
659
658
658
659
659
658
659
660
660
660
660
660
660
659
659
659
659
659
659
659
659
660
659
658
658
658
658
657
657
657
658
657
656
657
657
657
656
656
655
...

result:

ok 2000 numbers

Test #29:

score: 0
Accepted
time: 2ms
memory: 5704kb

input:

2000 2000
0 1 1 0 0 0 0 1 1 2 0 2 1 2 0 0 0 0 1 0 0 1 2 0 1 1 0 0 1 2 1 1 2 2 2 1 1 2 0 2 2 0 1 0 1 2 2 0 2 0 0 2 0 1 2 2 0 1 0 1 0 1 0 2 0 2 1 2 1 1 0 1 2 0 1 1 1 2 0 2 1 1 2 1 2 0 1 0 0 0 0 2 2 0 2 2 0 2 2 1 0 1 2 1 0 2 0 1 1 2 2 0 0 0 0 2 0 2 2 1 1 1 2 2 0 1 2 0 2 1 0 1 1 2 2 2 0 0 0 0 1 0 0 2 1 ...

output:

679
679
679
679
679
679
679
678
679
678
678
678
679
678
679
678
678
678
678
678
677
678
677
678
678
678
679
678
678
678
678
678
677
677
677
678
677
678
678
678
678
678
678
678
679
678
679
679
679
680
680
680
680
680
680
679
678
677
676
677
676
676
677
676
675
674
674
674
674
674
674
673
673
672
672
...

result:

ok 2000 numbers

Test #30:

score: -5
Wrong Answer
time: 34ms
memory: 5712kb

input:

10 200000
1 2 2 2 2 1 0 2 2 2
10 -1
3 0
5 0
10 -1
10 0
3 0
5 0
7 1
9 -2
10 2
2 -2
6 -1
6 0
8 -1
4 -2
2 0
5 -1
8 1
1 1
4 1
1 -2
3 0
4 1
9 0
9 0
6 1
7 -1
4 -2
2 1
6 0
8 0
3 0
5 -1
10 -1
5 2
9 1
1 0
6 -1
2 0
9 1
2 1
4 2
5 -2
7 1
3 0
1 2
9 0
5 1
1 -1
6 2
6 -2
9 -1
8 -2
6 1
2 -2
1 -1
10 -1
2 0
8 2
6 -1
2...

output:

5
5
5
4
4
4
4
5
4
5
4
4
4
3
2
2
2
3
3
3
3
3
3
3
3
3
3
2
3
3
3
3
2
2
3
3
3
2
2
3
3
4
3
4
4
4
4
5
4
5
4
3
2
3
2
2
2
2
3
2
2
3
2
3
2
2
3
3
3
3
2
3
3
3
2
2
2
1
1
1
2
1
1
1
0
0
0
0
1
1
1
1
2
2
2
2
2
2
2
2
2
2
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
2
2
2
2
2
3
3
3
2
2
3
3
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
4
4
4
3
3
4
...

result:

wrong answer 15th numbers differ - expected: '3', found: '2'

Subtask #4:

score: 0
Wrong Answer

Test #35:

score: 0
Wrong Answer
time: 0ms
memory: 5784kb

input:

2000 1999
0 1 0 3 0 1 0 0 0 0 0 0 0 2 0 0 0 0 3 1 1 0 2 0 0 3 0 0 0 0 0 4 0 0 1 0 1 0 0 0 0 1 2 1 0 0 0 0 7 0 1 3 1 0 1 1 0 3 2 1 0 1 1 3 3 1 0 2 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 1 2 3 0 1 0 3 3 0 0 0 0 1 0 1 2 0 0 2 2 0 1 2 1 2 0 0 0 1 1 0 1 2 0 0 0 0 2 0 5 0 0 0 0 0 1 0 0 2 0 1 2 0 1 0 0 0 2 0 ...

output:

666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
665
665
665
665
665
665
665
665
665
665
665
665
665
665
665
665
665
666
666
666
666
666
666
666
666
666
666
666
666
666
665
...

result:

wrong answer 812th numbers differ - expected: '632', found: '631'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%