QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #40063 | #2831. Game Theory | hit47 | WA | 58ms | 5804kb | C++ | 1.8kb | 2022-07-16 00:39:21 | 2022-07-16 00:39:22 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
const ll mod=998244353,N=2e5+10;
using namespace std;
int tree[N*4],lan[N*4],n;
char s[N];
void build(int root,int l,int r)
{
lan[root]=0;
if(l==r){
tree[root]=(int)(s[l]-'0');
return;
}
int mid=l+r>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
tree[root]=tree[root<<1]+tree[root<<1|1];
}
void update(int root,int l,int r,int left,int right)
{
if(lan[root])
{
lan[root]=0;
int mid=l+r>>1;
if(l!=r)lan[root<<1]=1,lan[root<<1|1]=1,tree[root<<1]=mid+1-l-tree[root<<1],tree[root<<1|1]=r-mid-tree[root<<1|1];
}
if(l>=left && r<=right)
{
tree[root]=r+1-l-tree[root];lan[root]=1;
return;
}
if(l>right || r<left)return;
int mid=l+r>>1;
update(root<<1,l,mid,left,right);
update(root<<1|1,mid+1,r,left,right);
tree[root]=tree[root<<1]+tree[root<<1 | 1];
}
int query(int root,int l,int r,int left,int right)
{
if(lan[root])
{
lan[root]=0;
int mid=l+r>>1;
if(l!=r)lan[root<<1]=1,lan[root<<1|1]=1,tree[root<<1]=mid+1-l-tree[root<<1],tree[root<<1|1]=r-mid-tree[root<<1|1];
}
if(l>=left && r<=right)return tree[root];
if(l>right || r<left)return 0;
int mid=l+r>>1;
return query(root<<1,l,mid,left,right)+query(root<<1|1,mid+1,r,left,right);
}
long long erfen(int l,int r)
{
if(l==r)return 0;
int mid=l+r>>1;
return query(1,1,n,mid+1,r)*(mid+1-l-query(1,1,n,l,mid))+erfen(l,mid)+erfen(mid+1,r);
}
int main()
{
int q,i,j;
long long ans,k,t;
while(scanf("%d%d",&n,&q)!=EOF)
{
scanf("%s",s+1);
build(1,1,n);
k=0;
for(i=n;i>=1;--i)
if(s[i]=='1')ans++,k++;
else ans+=k;
for(i=1;i<=q;++i)
{
int l,r;
scanf("%d%d",&l,&r);
update(1,1,n,l,r);
ans=erfen(1,n)+query(1,1,n,1,n);
printf("%lld\n",ans%mod);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 5804kb
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: 2ms
memory: 5692kb
input:
1 1 0 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Wrong Answer
time: 58ms
memory: 5772kb
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 2 1 2 0 1 0 1 2 0 0 2 0 1 2 0 1 2 1 0 1 2 1 0 0 1 2 2 1 0 1 2 2 2 1 0 1 0 0 1 0 1 0 2 2 1 0 1 2 1 1 0 2 0 2 2 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 2 0 1 0 0 1 1 0 1 0 1 2 0 2 1 0 0 2 1 2 0 1 2 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 2 1 0 2 0 1 0 1 ...
result:
wrong answer 2nd lines differ - expected: '3', found: '2'