QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297365 | #6630. Triangle Collection | A_programmer | 0 | 34ms | 5872kb | C++17 | 1.9kb | 2024-01-04 12:30:11 | 2024-01-04 12:30:12 |
Judging History
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%