QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #347086 | #2831. Game Theory | xunxxxx | WA | 109ms | 3608kb | C++20 | 1.9kb | 2024-03-09 10:48:37 | 2024-03-09 10:48:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
#define N 1000010
#define lc p<<1
#define rc p<<1|1
int n,w[N];
string s;
struct node
{
int l,r,sum,add;
}tr[N*4];
void pushup(int p)//ÏòÉϸüÐÂ
{
tr[p].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(int p)//ÏòϸüÐÂ
{
if(tr[p].add)
{
tr[lc].sum=(tr[lc].r-tr[lc].l+1)-tr[lc].sum;
tr[rc].sum=(tr[rc].r-tr[rc].l+1)-tr[rc].sum;
tr[lc].add=tr[p].add;
tr[rc].add=tr[p].add;
tr[p].add=0;
}
}
void build(int p,int l,int r)
{
tr[p]={l,r,w[l],0};
if(l==r) return ;
int m=l+r>>1;
build(lc,l,m);
build(rc,m+1,r);
pushup(p);
}
void update(int p,int x,int k)//µ¥µãÐÞ¸Ä
{//¸ù½Úµã½øÈ룬½«½Úµã[x,x]¸ü¸ÄΪk£¬²¢¸ü¸ÄÆäËùÓÐ×æÏÈ
if(tr[p].l==x&&tr[p].r==x)
{
tr[p].sum+=k;//¸ü¸Ä
return ;
}
int m=tr[p].l+tr[p].r>>1;//µÝ¹éÕÒµ½Ò¶½Úµã[x,x]
if(x<=m) update(lc,x,k);
else update(rc,x,k);
tr[p].sum=tr[lc].sum+tr[rc].sum;//»ØËÝ
}
int query(int p,int x,int y)//Çø¼äÇóºÍ
{
if(x<=tr[p].l&&tr[p].r<=y) return tr[p].sum;//È«²¿¸²¸Ç£¬Ö±½Ó·µ»Ø
int m=tr[p].l+tr[p].r>>1;//²»ÊÇÍêÈ«¸²¸Ç£¬ÁÑ¿ª
pushdown(p);
int sum=0;
if(x<=m) sum+=query(lc,x,y);//×ó×ÓÊ÷Óв¿·Ö¸²¸Ç
if(y>m) sum+=query(rc,x,y);//ÓÒ×ÓÊ÷Óв¿·Ö¸²¸Ç
return sum;
}
void updatelr(int p,int x,int y)
{
if(x<=tr[p].l&&tr[p].r<=y)//¸²¸ÇÔòÐÞ¸Ä
{
tr[p].sum=(tr[p].r-tr[p].l+1)-tr[p].sum;
tr[p].add=1;
return ;
}
int m=tr[p].l+tr[p].r>>1;//²»¸²¸ÇÁÑ¿ª
pushdown(p);
if(x<=m) updatelr(lc,x,y);
if(y>m) updatelr(rc,x,y);
pushup(p);
}
signed main()
{
int n,q,op,x,y,k;
while(cin>>n>>q)
{
cin>>s;
for(int i=1;i<=n;i++) w[i]=s[i-1]-'0';
build(1,1,n);
while(q--)
{
cin>>x>>y;
updatelr(1,x,y);
cout<<query(1,1,n)<<"\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
3 2 010 1 2 2 3 5 1 00000 1 5
output:
1 3 5
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1 1 0 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Wrong Answer
time: 109ms
memory: 3608kb
input:
2 2 01 2 2 2 2 2 2 01 1 2 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 2 2 00 1 2 1 2 2 2 11 1 2 1 2 2 2 01 2 2 1 1 2 2 10 2 2 1 2 2 2 01 1 2 1 2 1 2 0 1 1 1 1 2 2 01 1 2 2 2 1 2 0 1 1 1 1 1 2 1 1 1 1 1 2 2 10 1 2 1 1 1 2 0 1 1 1 1 2 2 01 1 2 1 2 2 2 10 1 2 1 1 1 2 0 1 1 1 1 1 2 0 1 1 1 1 1 2 1 1 1 1 1 2 2 10 1 ...
output:
0 1 1 1 0 1 0 1 2 0 0 2 0 1 2 0 1 1 1 0 1 2 1 0 0 1 1 2 1 0 1 1 1 2 1 0 1 0 0 1 0 1 0 2 2 1 0 1 2 1 1 0 2 0 2 1 1 0 0 1 2 0 0 1 0 1 0 1 1 0 1 2 2 0 0 2 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 2 0 1 0 1 0 0 1 1 0 1 0 1 2 0 2 1 0 0 1 1 2 0 1 1 2 1 0 0 1 2 0 2 0 0 1 0 1 1 0 1 0 1 0 1 0 1 2 1 0 1 1 0 1 0 1 0 1 ...
result:
wrong answer 2nd lines differ - expected: '3', found: '1'