Submission #657347

#	Time	Username	Problem	Language	Result	Execution time	Memory
657347		S2speed	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1296 ms	169064 KiB

street_lamps

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cout<<"--------------------------------------\n";
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 3e5 + 17 , md = 1e9 + 7 , inf = 2e16;

struct fentree {
	
	ll sz;
	vector<ll> val;

	void init(ll n){
		sz = n;
		val.assign(sz , 0);
		return;
	}

	void add(ll i , ll k){
		ll h = i;
		while(h < sz){
			val[h] += k;
			h |= (h + 1);
		}
		return;
	}

	void add(ll l , ll r , ll k){
		add(l , k); add(r , -k);
		return;
	}

	ll cal(ll i){
		ll h = i , res = 0;
		while(~h){
			res += val[h];
			h &= (h + 1); h--;
		}
		return res;
	}

};

struct node {

	ll sz;
	vector<ll> v;
	fentree ft;

	void pre(ll i){
		v.push_back(i);
		return;
	}

	void build(){
		sort(all(v));
		v.resize(distance(v.begin() , unique(all(v))));
		sz = sze(v);
		ft.init(sz);
		return;
	}

	void add(ll l , ll r , ll k){
		l = lower_bound(all(v) , l) - v.begin(); r = lower_bound(all(v) , r) - v.begin();
		ft.add(l , r , k);
		return;
	}

	ll cal(ll i){
		i = upper_bound(all(v) , i) - v.begin() - 1;
		return ft.cal(i);
	}

};

struct segtree2d {

	ll sz = 1;
	vector<node> val;

	void init(ll n){
		while(sz < n) sz <<= 1;
		val.resize(sz << 1);
		return;
	}

	void pre(ll l , ll r , pll k , ll x , ll lx , ll rx){
		if(rx <= l || lx >= r) return;
		if(rx <= r && lx >= l){
			val[x].pre(k.first); val[x].pre(k.second);
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		pre(l , r , k , ln , lx , m); pre(l , r , k , rn , m , rx);
		return;
	}

	void pre(ll l , ll r , pll k){
		pre(l , r , k , 0 , 0 , sz);
		return;
	}

	void build(ll x , ll lx , ll rx){
		val[x].build();
		if(rx - lx == 1) return;
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		build(ln , lx , m); build(rn , m , rx);
		return;
	}

	void build(){
		build(0 , 0 , sz);
		return;
	}

	void add(ll l , ll r , plll k , ll x , ll lx , ll rx){
		if(rx <= l || lx >= r) return;
		if(rx <= r && lx >= l){
			val[x].add(k.first.first , k.first.second , k.second);
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		add(l , r , k , ln , lx , m); add(l , r , k , rn , m , rx);
		return;
	}

	void add(ll l , ll r , plll k){
		add(l , r , k , 0 , 0 , sz);
		return;
	}

	ll cal(ll i , ll j , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			return val[x].cal(j);
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		ll a;
		if(i < m){
			a = cal(i , j , ln , lx , m);
		} else {
			a = cal(i , j , rn , m , rx);
		}
		return a + val[x].cal(j);
	}

	ll cal(ll i , ll j){
		return cal(i , j , 0 , 0 , sz);
	}

};

struct segtree {

	ll sz = 1;
	vector<ll> val;

	void init(ll n){
		while(sz < n) sz <<= 1;
		val.assign(sz << 1 , inf);
		return;
	}

	void build(ll k , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			val[x] = lx + k;
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		build(k , ln , lx , m); build(k , rn , m , rx);
		return;
	}

	void build(ll k){
		build(k , 0 , 0 , sz);
		return;
	}

	void set(ll l , ll r , ll i , ll laz , ll x , ll lx , ll rx){
		if(laz != inf){
			val[x] = laz;
		}
		if(rx <= l || lx >= r) return;
		if(rx <= r && lx >= l){
			val[x] = i;
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		set(l , r , i , val[x] , ln , lx , m); set(l , r , i , val[x] , rn , m , rx);
		val[x] = inf;
		return;
	}

	void set(ll l , ll r , ll i){
		set(l , r , i , inf , 0 , 0 , sz);
		return;
	}

	ll cal(ll i , ll x , ll lx , ll rx){
		if(val[x] != inf) return val[x];
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		if(i < m) return cal(i , ln , lx , m);
		return cal(i , rn , m , rx);
	}

	ll cal(ll i){
		return cal(i , 0 , 0 , sz);
	}

	void clear(){
		sz = 1;
		val.clear();
		return;
	}

};

segtree2d st;
segtree lf , rt;
vector<pll> qu;
string s;
bitset<maxn> a;

void sefr_be_yek(ll i , ll t , bool p){
	ll lft = lf.cal(i) , rgt = rt.cal(i);
	lf.set(i + 1 , rgt + 1 , lft);
	rt.set(lft , i , rgt);
	if(p){
		st.pre(lft + 1 , i + 1 , {i + 1 , rgt + 1});
	} else {
//		if(t == 5){
//			cout<<lft + 1<<' '<<i + 1<<' '<<i<<' '<<rgt<<'\n';
//		}
		st.add(lft + 1 , i + 1 , {{i + 1 , rgt + 1} , -t});
	}
	return;
}

void yek_be_sefr(ll i , ll t , bool p){
	ll lft = lf.cal(i) , rgt = rt.cal(i);
	rt.set(lft , i , i);
	lf.set(i + 1 , rgt + 1 , i);
	if(p){
		st.pre(lft + 1 , i + 1 , {i + 1 , rgt + 1});
	} else {
		st.add(lft + 1 , i + 1 , {{i + 1 , rgt + 1} , t});
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	ll n , q;
	cin>>n>>q>>s;
	lf.init(n); rt.init(n);
	lf.build(-1); rt.build(1);
	st.init(n);
	for(ll i = 0 ; i < n ; i++){
		if(s[i] == '1'){
			a[i] = true;
			sefr_be_yek(i , 0 , true);
		}
	}
	for(ll e = 1 ; e <= q ; e++){
		string t;
		cin>>t;
		if(t[0] == 't'){
			ll i;
			cin>>i; i--;
			qu.push_back({i , -1});
			if(a[i]){
				yek_be_sefr(i , e , true);
				a[i] = false;
			} else {
				sefr_be_yek(i , e , true);
				a[i] = true;
			}
			continue;
		}
		ll l , r;
		cin>>l>>r; l--; r--;
		qu.push_back({l , r});
	}
	lf.clear(); rt.clear();
	lf.init(n); rt.init(n);
	lf.build(-1); rt.build(1);
	st.build();
//	for(auto i : st.val[9].v){
//		cout<<i<<' ';
//	}
//	cout<<'\n';
	a.reset();
	for(ll i = 0 ; i < n ; i++){
		if(s[i] == '1'){
			a[i] = true;
			sefr_be_yek(i , 0 , false);
		}
	}
	ll t = 0;
	for(auto p : qu){
		t++;
		if(p.second == -1){
			ll i = p.first;
			if(a[i]){
				yek_be_sefr(i , t , false);
				a[i] = false;
			} else {
				sefr_be_yek(i , t , false);
				a[i] = true;
			}
			continue;
		}
		ll l = p.first , r = p.second;
		ll h = st.cal(l , r);
		if(a[l] == 1){
			if(rt.cal(l) >= r){
				h += t;
			}
		}
		cout<<h<<'\n';
	}
	return 0;
}

/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

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