QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #21791 | #2831. Game Theory | Qyc_AK_NOI2022# | WA | 12ms | 3600kb | C++14 | 2.1kb | 2022-03-08 15:38:23 | 2022-05-08 04:04:37 |
Judging History
answer
#include <cstdio>
using namespace std;
typedef long long ll;
inline int rd(){
int x=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c==EOF)return -1;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
const int mod=998244353;
struct node{
bool tag;
int hv0,hv1,sum0,sum1;
}t[1000010];
int n,q,s[300010];
inline int rdc(){
char c=getchar();
while(c<'0'||c>'9')c=getchar();
return c^48;
}
inline int fx(int x){return x>=mod?x-mod:x;}
inline void refresh(int p){
t[p].sum0=fx(t[p<<1].sum0+t[p<<1|1].sum0);
t[p].sum1=fx(t[p<<1].sum1+t[p<<1|1].sum1);
t[p].hv0=t[p<<1].hv0+t[p<<1|1].hv0;
t[p].hv1=t[p<<1].hv1+t[p<<1|1].hv1;
}
inline void swp(int &x,int &y){x^=y^=x^=y;}
void build(int l,int r,int p){
if(l==r){
t[p]=(node){0,!s[l],s[l],(!s[l])*l,s[l]*l};
return;
}
int mid=l+r>>1;
t[p].tag=0;
build(l,mid,p<<1),build(mid+1,r,p<<1|1);
refresh(p);
}
inline void adt(int p){
t[p].tag^=1;
swp(t[p].hv0,t[p].hv1);
swp(t[p].sum0,t[p].sum1);
}
inline void pushdown(int p){
if(t[p].tag){
t[p].tag=0;
adt(p<<1),adt(p<<1|1);
}
}
void filp(int l,int r,int p,int b,int e){
if(b<=l && e>=r)return adt(p);
pushdown(p);
int mid=l+r>>1;
if(b<=mid)filp(l,mid,p<<1,b,e);
if(e>mid)filp(mid+1,r,p<<1|1,b,e);
refresh(p);
}
int qus0(int l,int r,int p,int e){
if(e>=r)return ((ll)(e+1)*t[p].hv0+mod-t[p].sum0)%mod;
pushdown(p);
int mid=l+r>>1,ans=qus0(l,mid,p<<1,e);
if(e>mid)ans=fx(ans+qus0(mid+1,r,p<<1|1,e));
return ans;
}
int qus1(int l,int r,int p,int b){
if(b<=l)return fx(t[p].sum1+mod-(ll)(b-1)*t[p].hv0%mod);
pushdown(p);
int mid=l+r>>1,ans=qus1(mid+1,r,p<<1|1,b);
if(b<=mid)ans=fx(ans+qus1(l,mid,p<<1,b));
return ans;
}
inline int qus0(int p){
if(!p)return 0;
return qus0(1,n,1,t[1].hv1-1);
}
inline int qus1(int p){
return qus1(1,n,1,t[1].hv1);
}
int main(){
while((n=rd())!=-1){
q=rd();
for(int i=1;i<=n;++i)s[i]=rdc();
build(1,n,1);
for(int i=1,l,r;i<=q;++i){
l=rd(),r=rd(),filp(1,n,1,l,r);
if(!t[1].hv1){puts("0");continue;}
printf("%d\n",fx(qus0(t[1].hv1-1)+qus1(t[1].hv1)));
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3536kb
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: 3600kb
input:
1 1 0 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Wrong Answer
time: 12ms
memory: 3556kb
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'