QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#124284 | #6630. Triangle Collection | starrylasky | 0 | 1ms | 9836kb | C++14 | 2.0kb | 2023-07-14 16:33:09 | 2023-07-14 16:33:11 |
Judging History
answer
///yl/hs/bx/yl
#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define LL long long
// #define int long long
#define ld long double
#define pr pair<int,int>
#define mpr make_pair
using namespace std;
const int N = 4e5+5,mod = 1e9+7;
inline int read()
{
int s=0,w=1; char ch=getchar();
while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1; ch=getchar();}
while( ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
return s*w;
}
inline int Mod(int x) {return x>=mod?x-mod:x;}
inline void addmod(int &x,int y) {x=Mod(x+y);}
namespace starrylasky
{
int n,Q,c[N];
struct SGT
{
#define lson u<<1
#define rson u<<1|1
#define mid (l+r>>1)
LL sl[N<<2],sr[N<<2],sd[N<<2];
inline void pushup(int u)
{
int res=min(sl[lson],sr[rson]);
sd[u]=sd[lson]+sd[rson]+res;
sl[u]=sl[lson]+sl[rson]-res;
sr[u]=sr[lson]+sr[rson]-res;
}
inline void work(int u)
{
int res=min(sl[u],sr[u]);
sl[u]-=res; sr[u]-=res; sd[u]+=res;// cerr<<sl[u]<<" "<<sr[u]<<" "<<sd[u]<<"\n";
}
inline void update(int u,int l,int r,int pos)
{
if(l==r) return sl[u]=c[l]&1,sr[u]=(l&1?c[l+1>>1]>>1:0),sd[u]=0,work(u);
if(mid>=pos) update(lson,l,mid,pos);
else update(rson,mid+1,r,pos);
pushup(u);
}
}sgt;
inline void Main()
{
n=read(),Q=read();
fep(i,1,n) c[i]=read();
fep(i,1,2*n) sgt.update(1,1,2*n,i);
fep(i,1,Q)
{
int p=read(),v=read(); c[p]+=v;
sgt.update(1,1,n,p); sgt.update(1,1,n,2*p-1);
printf("%lld\n",sgt.sd[1]+2*sgt.sr[1]/3);
}
}
}
signed main()
{
int _T=1;
while(_T--) starrylasky::Main();
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 1ms
memory: 5768kb
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: -5
Wrong Answer
time: 0ms
memory: 9680kb
input:
12 1 13 79 59 21 32 13 85 40 74 15 49 56 3 31
output:
204
result:
wrong answer 1st numbers differ - expected: '189', found: '204'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #28:
score: 0
Wrong Answer
time: 1ms
memory: 9796kb
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 661 661 661 661 660 660 660 660 661 661 663 664 665 665 664 663 663 663 664 663 663 662 662 663 663 664 664 664 663 662 662 662 661 660 659 658 657 657 656 655 654 654 654 654 654 654 653 653 653 653 652 652 651 651 651 652 651 650 650 650 651 649 648 648 647 648 648 648 648 648 647 647 646 ...
result:
wrong answer 3rd numbers differ - expected: '660', found: '661'
Subtask #4:
score: 0
Wrong Answer
Test #35:
score: 0
Wrong Answer
time: 1ms
memory: 9836kb
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 665 665 665 666 666 667 666 667 667 667 667 667 667 667 667 667 670 669 668 668 667 666 665 665 664 663 663 664 663 664 663 663 663 663 661 662 661 661 661 661 658 658 657 657 657 657 657 657 656 656 656 656 656 656 656 657 657 658 659 658 656 656 656 656 656 656 656 656 655 654 654 ...
result:
wrong answer 5th numbers differ - expected: '666', found: '665'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%