QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116633 | #6630. Triangle Collection | lmeowdn# | 5 | 136ms | 21016kb | C++14 | 2.6kb | 2023-06-29 17:20:41 | 2024-05-31 18:29:30 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2e5+5;
int n,Q,cnt,sum,yc[N],ys[N],a[N];
namespace SegT {
int ls[N<<1],rs[N<<1],s[N<<1],tag[N<<1],tot=1;
void build(int p,int l,int r) {
if(l==r) {s[p]=yc[l]-ys[l/2+1]; return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=max(s[ls[p]],s[rs[p]]);
}
void add(int p,int z) {s[p]+=z; tag[p]+=z;}
void psd(int p) {add(ls[p],tag[p]), add(rs[p],tag[p]), tag[p]=0;}
void add(int p,int l,int r,int x,int y,int z) {
if(l==x&&r==y) {add(p,z); return;} int mid=l+r>>1; psd(p);
if(y<=mid) add(ls[p],l,mid,x,y,z);
else if(x>mid) add(rs[p],mid+1,r,x,y,z);
else add(ls[p],l,mid,x,mid,z), add(rs[p],mid+1,r,mid+1,y,z);
s[p]=max(s[ls[p]],s[rs[p]]);
}
int qry() {return max(0ll,s[1]);}
}
signed main() {
n=read(), Q=read();
rep(i,1,n) a[i]=read();
per(i,n,1) yc[i]=yc[i+1]+a[i]%2;
per(i,n,1) ys[i]=ys[i+1]+a[i]/2;
per(i,n,1) ys[i]=ys[i/2+1];
cnt=yc[1], sum=ys[1]*2;
SegT::build(1,1,n);
rep(i,1,Q) {
int l=read(), d=read();
if(a[l]&1) SegT::add(1,1,n,1,l,-1), cnt--;
SegT::add(1,1,n,1,min(2*l-1,n),a[l]/2), sum-=a[l]/2*2;
a[l]+=d;
if(a[l]&1) SegT::add(1,1,n,1,l,1), cnt++;
SegT::add(1,1,n,1,min(2*l-1,n),-a[l]/2), sum+=a[l]/2*2;
int p=cnt-SegT::qry();
int ans=p+(sum-2*p)/3;
printf("%lld\n",ans);
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 7776kb
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: 2ms
memory: 11924kb
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: 0ms
memory: 11988kb
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: 2ms
memory: 12004kb
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: 2ms
memory: 12216kb
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: -5
Wrong Answer
time: 2ms
memory: 12256kb
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:
wrong answer 592nd numbers differ - expected: '653', found: '654'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #28:
score: 5
Accepted
time: 2ms
memory: 12276kb
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: 12352kb
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: 19ms
memory: 12216kb
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 3 3 2 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 2 2 3 3 3 3 3 3 3 4 3 4 4 4 4 5 4 5 4 4 3 3 2 2 2 2 3 3 3 3 2 3 2 2 2 2 2 2 2 3 3 3 2 2 2 1 1 1 1 0 0 0 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 166th numbers differ - expected: '2', found: '3'
Subtask #4:
score: 5
Accepted
Test #35:
score: 5
Accepted
time: 3ms
memory: 12088kb
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:
ok 1999 numbers
Test #36:
score: 0
Accepted
time: 2ms
memory: 12244kb
input:
1999 2000 938865181 635701131 720186551 12098533 888342577 819466162 677119886 695501777 87063160 544120940 280740814 953384275 462378756 394423771 769842478 563100233 988726627 938258387 941725041 202877851 608668845 507891555 488072389 600920090 738211573 440041095 584208199 334345340 587249363 60...
output:
334310744804 334310744804 334310744805 334310744805 334310744805 334310744805 334310744805 334310744806 334310744805 334310744805 334310744805 334310744805 334310744805 334310744805 334310744805 334310744805 334310744805 334310744805 334310744805 334310744804 334310744805 334310744804 334310744805 3...
result:
ok 2000 numbers
Test #37:
score: 0
Accepted
time: 2ms
memory: 12276kb
input:
1998 2000 953983734 995770518 938631730 961951570 959332856 972648102 943061680 904445058 924304353 960622114 906426330 931936027 957313612 965894280 965137632 988149861 916855162 928712995 923621242 962852409 971372933 948162818 943268160 970351693 997138667 985041992 953192885 954772005 986919660 ...
output:
632914970666 632914970667 632914970666 632914970666 632914970666 632914970665 632914970666 632914970666 632914970666 632914970667 632914970667 632914970667 632914970666 632914970667 632914970666 632914970667 632914970667 632914970667 632914970668 632914970667 632914970668 632914970667 632914970667 6...
result:
ok 2000 numbers
Test #38:
score: 0
Accepted
time: 2ms
memory: 12280kb
input:
2000 1999 0 5 4 1 3 4 1 3 1 0 0 1 4 0 3 5 5 2 3 0 5 3 3 4 5 3 5 5 0 3 4 5 4 0 2 0 0 4 0 5 5 2 2 3 5 5 4 0 3 2 2 2 0 4 5 4 2 2 5 1 5 5 1 4 5 2 0 4 3 1 5 4 5 1 0 3 0 5 2 4 3 0 4 1 2 5 4 1 4 4 1 0 4 1 0 3 5 5 5 3 4 5 5 1 5 5 5 0 0 2 5 0 3 3 2 4 2 1 3 5 3 4 2 5 2 3 2 3 4 5 1 1 2 3 4 3 3 4 2 0 4 0 0 2 1 ...
output:
1655 1655 1656 1656 1656 1655 1655 1655 1656 1656 1656 1655 1656 1656 1656 1657 1657 1657 1657 1657 1658 1657 1658 1657 1657 1657 1657 1657 1657 1657 1656 1657 1656 1656 1656 1655 1656 1656 1656 1656 1656 1657 1657 1657 1657 1657 1658 1657 1657 1657 1657 1657 1657 1657 1657 1657 1657 1657 1657 1657 ...
result:
ok 1999 numbers
Test #39:
score: 0
Accepted
time: 122ms
memory: 20860kb
input:
200000 200000 1 4 9 4 6 9 5 8 4 7 8 5 8 4 5 0 10 1 2 5 5 6 2 1 2 5 7 7 5 9 6 6 1 4 6 6 4 2 10 9 6 0 9 10 1 5 7 4 7 5 9 10 0 2 6 10 4 3 7 2 7 7 10 0 5 1 2 2 0 8 10 6 7 4 4 10 0 7 0 8 8 8 6 5 6 5 1 5 10 5 9 3 9 3 6 6 7 7 9 7 5 7 0 7 1 3 7 9 5 0 0 9 10 3 5 3 2 1 8 4 1 0 8 5 7 6 1 1 4 5 1 6 5 3 6 1 5 5 ...
output:
332845 332845 332846 332845 332845 332845 332844 332844 332844 332845 332844 332845 332844 332844 332844 332843 332843 332843 332842 332842 332842 332842 332842 332843 332843 332843 332844 332843 332843 332843 332844 332843 332843 332843 332842 332843 332842 332842 332842 332842 332842 332841 332842...
result:
ok 200000 numbers
Test #40:
score: 0
Accepted
time: 132ms
memory: 21016kb
input:
200000 200000 85713646 336686856 538585247 278110438 233218655 716436104 837912968 251689084 911446322 701433421 627692917 334396123 413292301 8832435 188412011 689794769 286917079 209754313 519445483 105763643 27705054 168552468 752722351 829700685 747331109 706042730 418755558 614136831 2655911 80...
output:
33341754832470 33341754832470 33341754832471 33341754832470 33341754832471 33341754832470 33341754832470 33341754832470 33341754832470 33341754832470 33341754832470 33341754832470 33341754832471 33341754832470 33341754832471 33341754832470 33341754832471 33341754832471 33341754832471 33341754832472 ...
result:
ok 200000 numbers
Test #41:
score: 0
Accepted
time: 127ms
memory: 20928kb
input:
200000 200000 635910513 530707612 43308926 653927427 953772413 886338816 149455282 24772774 715587632 555119024 702589377 349422399 13059257 305480192 768707679 77455076 588537505 275449414 881106189 997605463 699449988 579049544 439144233 339940611 677203754 952180230 954696649 608213997 944927273 ...
output:
33346597165806 33346597165806 33346597165806 33346597165805 33346597165805 33346597165805 33346597165804 33346597165804 33346597165804 33346597165803 33346597165803 33346597165803 33346597165802 33346597165802 33346597165802 33346597165801 33346597165801 33346597165801 33346597165800 33346597165800 ...
result:
ok 200000 numbers
Test #42:
score: 0
Accepted
time: 135ms
memory: 20948kb
input:
200000 200000 323842684 404575711 975846485 26692339 484624497 479820673 79145839 690422479 435950749 721344329 55972947 946532807 537527876 632207792 134109985 92150997 282767325 50309244 942832532 291033288 394196176 355961510 210549616 639079458 254823064 129598231 941770957 38138695 661229827 98...
output:
33357361283426 33357361283426 33357361283427 33357361283427 33357361283427 33357361283428 33357361283428 33357361283428 33357361283429 33357361283429 33357361283429 33357361283430 33357361283430 33357361283430 33357361283431 33357361283431 33357361283431 33357361283432 33357361283432 33357361283432 ...
result:
ok 200000 numbers
Test #43:
score: 0
Accepted
time: 136ms
memory: 20996kb
input:
200000 200000 1000000000 1000000000 1000000000 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 999999999 1000000000 999999999 1000000000 1000000000 999999999 999999999 1000000000 1000000000 999999999 1000000000 999999999 1000000000 1000000000 1000000000 1000000000 1000000...
output:
66666666633339 66666666633339 66666666633339 66666666633338 66666666633338 66666666633338 66666666633339 66666666633339 66666666633339 66666666633339 66666666633339 66666666633339 66666666633339 66666666633339 66666666633339 66666666633339 66666666633339 66666666633339 66666666633339 66666666633338 ...
result:
ok 200000 numbers
Subtask #5:
score: 0
Skipped
Dependency #1:
0%