Submission #258181

#	Time	Username	Problem	Language	Result	Execution time	Memory
258181		amoo_safar	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	4502 ms	187080 KiB

street_lamps

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef string str;
typedef pair<int, int> pii;

const int N = 3e5 + 10;

int n, q;
str s;

typedef pair<int, pii> Event;

vector<Event> E;
set<pii> st;

pii Find(int idx){
	return  *(--st.upper_bound({idx, n + n}));
}

vector< pair<int, pii> > F[N];
int Timer = 0;

void Add2(int i, int j, int d){
	for(; i < N; i += i & (-i))
		F[i].pb({Timer, {(d == 1 ? -2 : -1), j}});
}
void Ask2(int i, int j, int id){
	for(; i; i -= (i & (-i)))
		F[i].pb({Timer, {id, j}});
}

int fen[N], sh[N], ans[N];
void Add(int idx, int d){
	for(; idx < N; idx += (idx & (-idx))){
		if(d == -1) fen[idx] += Timer;
		else fen[idx] -= Timer - 1; 
		sh[idx] += d;
	}
}
void Reset(int idx){
	for(; idx < N; idx += (idx & (-idx))){
		fen[idx] = 0;
		sh[idx] = 0;
	}
}
int Get(int idx){
	int res = 0;
	for(; idx; idx -= (idx & (-idx)))
		res += fen[idx] + sh[idx] * Timer;
	return res;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	cin >> s; s = "0" + s + "0";
	
	vector<pii> V;
	for(int i = 0; i + 1 < n + 2; i++){
		cerr << i << ' ' << s[i] << ' ' << s[i + 1] << '\n';
		if(s[i] == '0' && s[i + 1] == '1')
			V.pb(pii(i + 1, -1));
		if(s[i] == '1' && s[i + 1] == '0')
			V[V.size() - 1].S = i;
	}

	for(auto x : V){
		E.pb({+1, {x.F, n + 1 - x.S}});
		st.insert(x);
	}
	//E.pb({2, {0, 0}});

	str type;
	int l, r, L, R;
	pii bl;
	for(int i = 0; i < q; i++){
		cin >> type;
		if(type == "query"){
			cin >> l >> r; r--;
			E.pb({0, {l, n + 1 - r}});
			E.pb({2, {0, 0}});
			continue;
		}
		cin >> l;
		if(s[l] == '1'){
			s[l] = '0';
			bl = Find(l);
			st.erase(bl);

			E.pb({-1, {bl.F, n + 1 - bl.S}});
			E.pb({2, {0, 0}});
		
			if(bl.F < l){
				st.insert({bl.F, l - 1});
				E.pb({+1, {bl.F, n + 1 - (l - 1)}});
			}
			if(bl.S > l){
				st.insert({l + 1, bl.S});
				E.pb({+1, {l + 1, n + 1 - bl.S}});
			}
			//E.pb({2, {0, 0}});
			continue;
		}
		s[l] = '1';
		L = l, R = l;

		if(s[l - 1] == '1'){
			bl = Find(l - 1);
			E.pb({-1, {bl.F, n + 1 - bl.S}});
			st.erase(bl);
			L = bl.F;
		}
		if(s[l + 1] == '1'){
			bl = Find(l + 1);
			E.pb({-1, {bl.F, n + 1 - bl.S}});
			st.erase(bl);
			R = bl.S;
		}
		E.pb({2, {0, 0}});
		
		E.pb({+1, {L, n + 1 - R}});
		st.insert({L, R});
		
		//E.pb({2, {0, 0}});
	}

	int cnt = 0;
	for(auto x : E){
		if(x.F == 2){
			Timer ++;
			continue;
		}
		if(x.F == 0)
			Ask2(x.S.F, x.S.S, cnt ++);
		else
			Add2(x.S.F, x.S.S, x.F);
	}

	for(int i = 1; i < N; i++){
		for(auto &x : F[i]){
			Timer = x.F;
			if(x.S.F >= 0){
				ans[x.S.F] += Get(x.S.S);
			} else {
				Add(x.S.S, (x.S.F == -2 ? 1 : -1));
			}
		}
		//if(!F[i].empty()){
		//	memset(fen, 0, sizeof fen);
		//	memset(sh, 0, sizeof sh);
		//}
		
		for(auto &x : F[i]){
			if(x.S.F < 0)
				Reset(x.S.S);
		}
		
	}
	for(int i = 0; i < cnt; i++) cout << ans[i] << '\n';
	return 0;
}
/*
5 2
11111
toggle 3
query 1 6

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