QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #62246 | #2831. Game Theory | microne# | WA | 45ms | 9816kb | C++20 | 2.6kb | 2022-11-17 18:02:19 | 2022-11-17 18:02:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct dat
{
int one,zero,tag,onenum,zeronum;
}tr[1000005<<2];
const long long mod=998244353;
int n,m,a[1000005],one[1000005],zero[1000005];
void update(int p)
{
tr[p].one=((long long)tr[p<<1].one+tr[p<<1|1].one)%mod;
tr[p].zero=((long long)tr[p<<1].zero+tr[p<<1|1].zero)%mod;
tr[p].onenum=tr[p<<1].onenum+tr[p<<1|1].onenum;
tr[p].zeronum=tr[p<<1].zeronum+tr[p<<1|1].zeronum;
}
void build(int p,int l,int r)
{
tr[p].tag=0;
if (l==r)
{
tr[p].one=one[l];
tr[p].zero=zero[r];
if (tr[p].one!=0) { tr[p].onenum=1; tr[p].zeronum=0; }
else { tr[p].zeronum=1; tr[p].onenum=0; }
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
update(p);
}
void pushdown(int p)
{
if (tr[p].tag)
{
tr[p].tag=0;
tr[p<<1].tag^=1;
tr[p<<1|1].tag^=1;
swap(tr[p<<1].one,tr[p<<1].zero);
swap(tr[p<<1|1].one,tr[p<<1|1].zero);
swap(tr[p<<1].onenum,tr[p<<1|1].onenum);
swap(tr[p<<1].zeronum,tr[p<<1|1].zeronum);
}
}
void change(int p,int l,int r,int L,int R)
{
if (l>=L&&r<=R)
{
swap(tr[p].one,tr[p].zero);
swap(tr[p].onenum,tr[p].zeronum);
tr[p].tag=1;
return;
}
pushdown(p);
int mid=l+r>>1;
if (L<=mid) change(p<<1,l,mid,L,R);
if (R>mid) change(p<<1|1,mid+1,r,L,R);
update(p);
}
struct res
{
long long one,zero;
};
res ask(int p,int l,int r,int L,int R)
{
if (l>r) { return {0,0}; }
if (l==r) { return {tr[p].one,tr[p].zero}; }
if (l>=L&&r<=R)
{
return {tr[p].one,tr[p].zero};
}
pushdown(p);
int mid=l+r>>1;
res ans={0,0},sum={0,0};
if (L<=mid) ans=ask(p<<1,l,mid,L,R);
if (R>mid) sum=ask(p<<1|1,mid+1,r,L,R);
return {(long long)(ans.one+sum.one)%mod,(long long)(ans.zero+sum.zero)%mod};
}
/*
int query(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return tr[]
}*/
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
getchar();
for (int i=1;i<=n;++i)
{
zero[i]=one[i]=0;
}
for (int i=1;i<=n;++i)
{
char ch;
ch=getchar();
a[i]=ch-'0';
if (a[i]==1) one[i]=i;
if (a[i]==0) zero[i]=i;
}
build(1,1,n);
for (int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
change(1,1,n,x,y);
int k=tr[1].onenum;
if (k==n) { printf("%d\n",n); continue; }
if (k==0) { printf("0\n"); continue; }
if (ask(1,1,n,k,k).zero==k)
{
int lzero=ask(1,1,n,1,k-1).zero;
int rone=ask(1,1,n,k+1,n).one;
printf("%d\n",(rone*2-(2*lzero+k)+mod)%mod);
}
else
{
int lzero=ask(1,1,n,1,k-1).zero;
int rone=ask(1,1,n,k+1,n).one;
printf("%d\n",(rone*2+k-2*lzero+mod)%mod);
}
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 9652kb
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: 3ms
memory: 9632kb
input:
1 1 0 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Wrong Answer
time: 45ms
memory: 9816kb
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'