Submission #741882

#TimeUsernameProblemLanguageResultExecution timeMemory
741882jamezzzModern Machine (JOI23_ho_t5)C++17
0 / 100
9 ms1364 KiB
#include <bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define fi first #define se second #define pb push_back #define INF 2023456789 #define all(x) x.begin(),x.end() typedef pair<int,int> ii; typedef long long ll; #define maxn 120005 int n,m,q,c[maxn],a[maxn]; struct node{ int s,e,m,v,lz; node *l,*r; node(int _s,int _e){ s=_s,e=_e,m=(s+e)>>1,lz=-1; if(s!=e){ l=new node(s,m),r=new node(m+1,e); v=l->v+r->v; } else v=c[s]; } void ppo(){ if(lz!=-1){ v=(e-s+1)*lz; if(s!=e){ l->lz=lz; r->lz=lz; } lz=-1; } } void up(int x,int y,int nv){ if(s==x&&e==y){lz=nv;return;} if(y<=m)l->up(x,y,nv); else if(x>m)r->up(x,y,nv); else l->up(x,m,nv),r->up(m+1,y,nv); l->ppo(),r->ppo(); v=l->v+r->v; } int qry(int x,int y){ if(x>y)return 0; ppo(); if(s==x&&e==y)return v; if(y<=m)return l->qry(x,y); if(x>m)return r->qry(x,y); return l->qry(x,m)+r->qry(m+1,y); } int findR(int num){ ppo(); if(s==e){ if(num==1&&v==0)return s; else return -1; } l->ppo(),r->ppo(); int lnum=l->e-l->s+1-l->v; if(lnum>=num)return l->findR(num); else return r->findR(num-lnum); } int findB(int num){ ppo(); if(s==e){ if(num==1&&v==1)return s; else return -1; } l->ppo(),r->ppo(); if(l->v>=num)return l->findB(num); else return r->findB(num-l->v); } }*rt; int main(){ sf("%d%d",&n,&m); for(int i=1;i<=n;++i){ char ch;sf(" %c",&ch); c[i]=(ch=='B'); } for(int i=1;i<=m;++i)sf("%d",&a[i]); sf("%d",&q); for(int _=0;_<q;++_){ int l,r;sf("%d%d",&l,&r); rt=new node(1,n); for(int i=l;i<=r;++i){ rt->up(a[i],a[i],0); int lv=a[i]-1-rt->qry(1,a[i]-1);//number of R int rv=rt->qry(a[i]+1,n);//number of B if(rv<=lv){//the rv-th R to n become B int x=lv-rv+1; int p=rt->findR(x); rt->up(p,n,1); } else{//1 to the lv+1-th B become R int x=rt->qry(1,a[i])+lv+1; int p=rt->findB(x); rt->up(1,p,0); } } pf("%d\n",n-rt->qry(1,n)); } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:79:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  sf("%d%d",&n,&m);
      |    ^
Main.cpp:81:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   char ch;sf(" %c",&ch);
      |             ^
Main.cpp:84:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  for(int i=1;i<=m;++i)sf("%d",&a[i]);
      |                         ^
Main.cpp:85:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  sf("%d",&q);
      |    ^
Main.cpp:87:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   int l,r;sf("%d%d",&l,&r);
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...