QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #40069 | #2831. Game Theory | hit47 | WA | 52ms | 7812kb | C++ | 1.8kb | 2022-07-16 01:01:50 | 2022-07-16 01:01:51 |
Judging History
answer
#pragma GCC optimize(2)
#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];
}
long long 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;
long long l1=query(1,1,n,l,mid),r1=query(1,1,n,mid+1,r);
long long res=0;
res+=r1*(mid+1-l-l1);
if(l1)res+=erfen(l,mid);
if(r1)res+=erfen(mid+1,r);
return res;
}
int main()
{
int q,i,j;
long long ans,t;
while(scanf("%d%d",&n,&q)!=EOF)
{
scanf("%s",s+1);
build(1,1,n);
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);
}
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5768kb
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: 1ms
memory: 7812kb
input:
1 1 0 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Wrong Answer
time: 52ms
memory: 5856kb
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'