제출 #259470

#제출 시각아이디문제언어결과실행 시간메모리
259470Goolakh가로등 (APIO19_street_lamps)C++17
20 / 100
3061 ms244440 KiB
// FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP _ Who? _ // FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP _ You _ #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math") #define F first #define S second #define pb push_back #define SZ(x) (ll)(x.size()) #define all(x) x.begin(),x.end() #define MP make_pair typedef long long ll; typedef long double ld; typedef pair<ll,ll> pll; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn=3e5+10, maxm=1e6+10, lg=21, mod=998244353, inf=1e18; #define git(x) (x&-x) #define lc (v<<1) #define rc (lc^1) #define md ((s+t)>>1) struct node{ vector<ll> vec,bit; bool ok=0; void add(ll i,ll x){for(i++;i<SZ(bit);i+=git(i))bit[i]+=x;} ll get(ll i){ll ret=0;for(i++;i;i-=git(i))ret+=bit[i];return ret;} }seg[maxn<<2]; ll n,q,l[maxn],r[maxn]; string S; vector<ll> qq[maxn]; void rev(ll x,ll s=1,ll t=n+1,ll v=1){ if(t-s==1){ seg[v].ok^=1; return; } (x<md ? rev(x,s,md,lc):rev(x,md,t,rc)); seg[v].ok=seg[lc].ok&seg[rc].ok; } ll getc(ll x,ll s=1,ll t=n+1,ll v=1){ if(s>=x || seg[v].ok) return 0; if(t-s==1) return s; ll xx=getc(x,md,t,rc); if(xx!=0) return xx; return getc(x,s,md,lc); } ll getr(ll x,ll s=1,ll t=n+1,ll v=1){ if(t<=x+1 || seg[v].ok) return n+1; if(t-s==1) return s; ll xx=getr(x,s,md,lc); if(xx!=n+1) return xx; return getr(x,md,t,rc); } bool geto(ll l,ll r,ll s=1,ll t=n+1,ll v=1){ if(l>=t || r<=s) return 1; if(l<=s && r>=t) return seg[v].ok; return geto(l,r,s,md,lc) && geto(l,r,md,t,rc); } void bild(ll s=1,ll t=n+1,ll v=1){ if(t-s==1){ for(auto r:qq[s]) seg[v].vec.pb(r); sort(all(seg[v].vec)), seg[v].vec.resize(unique(all(seg[v].vec))-seg[v].vec.begin()); seg[v].bit.resize(SZ(seg[v].vec)+10); return; } bild(s,md,lc), bild(md,t,rc); seg[v].vec.resize(SZ(seg[lc].vec)+SZ(seg[rc].vec)); merge(all(seg[lc].vec),all(seg[rc].vec),seg[v].vec.begin()); seg[v].bit.resize(SZ(seg[v].vec)+10); } void add(ll l,ll r,ll lx,ll rx,ll x,ll s=1,ll t=n+1,ll v=1){ if(l>=t || r<=s) return; if(l<=s && r>=t){ ll L=upper_bound(all(seg[v].vec),lx)-seg[v].vec.begin(); ll R=upper_bound(all(seg[v].vec),rx)-seg[v].vec.begin(); seg[v].add(L,+x); seg[v].add(R,-x); return; } add(l,r,lx,rx,x,s,md,lc); add(l,r,lx,rx,x,md,t,rc); } ll get(ll l,ll r,ll s=1,ll t=n+1,ll v=1){ ll ret=seg[v].get(lower_bound(all(seg[v].vec),r)-seg[v].vec.begin()); if(t-s==1) return ret; ret+=(l<md ? get(l,r,s,md,lc):get(l,r,md,t,rc)); return ret; } int main(){ ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>q>>S; S='#'+S; for(int i=0;i<q;i++){ string s; cin>>s>>l[i]; if(s[0]=='q') cin>>r[i], qq[l[i]].pb(r[i]); } bild(); for(int i=1;i<=n;i++)if(S[i]=='1') add(getc(i)+1,i+1,i,getr(i),q), rev(i); for(int i=0;i<q;i++){ if(r[i]){ ll x=get(l[i],r[i]); if(x!=0) x+=(geto(l[i],r[i]) ? -1:+1)*(q-i-1); cout<<x<<'\n'; } else add(getc(l[i])+1,l[i]+1,l[i],getr(l[i]),(geto(l[i],l[i]+1) ? -1:+1)*(q-i-1)), rev(l[i]); } return 0; }
#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...