Submission #259481

#	Time	Username	Problem	Language	Result	Execution time	Memory
259481		Goolakh	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	3064 ms	244044 KiB

street_lamps

// 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(geto(l[i],r[i])) x-=(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;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20