Submission #158046

#	Time	Username	Problem	Language	Result	Execution time	Memory
158046		nvmdava	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1660 ms	311492 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
 
#define N 300005
#define INF 0x3f3f3f3f3f3f3f3f

struct Node{
	Node *l = NULL, *r = NULL;
	int val = 0;

	int query(int le, int ri, int x){

		if(le == ri) return val;
		int m = (le + ri) >> 1;
		if(m < x)
			return val + (r == NULL ? 0 : r -> query(m + 1, ri, x));
		return val + (l == NULL ? 0 : l -> query(le, m, x));
	}

	void update(int le, int ri, int R, int v){
		if(ri <= R){
			val += v;
			return;
		}

		int m = (le + ri) >> 1;
		
		if(l == NULL)
			l = new Node();
		l -> update(le, m, R, v);

		if(m < R){
			if(r == NULL)
				r = new Node();
			r -> update(m + 1, ri, R, v);
		}
	}
} *ans[N << 2];

int n, q;

void update(int id, int l, int r, int L, int R, int val){
	if(L <= l && r <= R){
		ans[id] -> update(1, n, R, val);
		return;
	}
	if(r < L || l > R){
		return;
	}
	int m = (l + r) >> 1;
	update(id << 1, l, m, L, R, val);
	update(id << 1 | 1, m + 1, r, L, R, val);
}

int query(int id, int l, int r, int x, int a){
	if(l == r){
		return ans[id] -> query(1, n, a);
	}
	int m = (l + r) >> 1;

	if(m < x)
		return ans[id] -> query(1, n, a) + query(id << 1 | 1, m + 1, r, x, a);
	return ans[id] -> query(1, n, a) + query(id << 1, l, m, x, a);
}

set<pair<pair<int, int>, int> > s;
int t;

void remove(set<pair<pair<int, int>, int> >::iterator it){
	update(1, 1, n, it -> ff.ss, it -> ff.ff, t - it -> ss);
	s.erase(it);
}

int st[N];

pair<int, int> tmp;

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

	cin>>n>>q;
	tmp.ff = n + 1;

	for(int i = 1; i < (n << 2); ++i)
		ans[i] = new Node();

	for(int i = 1; i <= n; i++){
		char c;
		cin>>c;
		st[i] = c - '0';
		if(st[i] == 1){
			if(tmp.ff > n)
				tmp.ss = i;
			tmp.ff = i;
		} else {
			if(tmp.ff <= n){
				s.insert({tmp, 0});
				tmp.ff = n + 1;
			}
		}
	}
	
	if(tmp.ff <= n)
		s.insert({tmp, 0});



	for(t = 1; t <= q; t++){
		string q;
		int a, b;
		cin>>q;
		if(q[0] == 'q'){
			cin>>a>>b;
			b--;
			auto it = s.lower_bound({{a, 0}, 0});
			if(it == s.end())
				cout<<query(1, 1, n, a, b)<<'\n';
			else
				cout<<query(1, 1, n, a, b) + (it -> ff.ss <= a && it -> ff.ff >= b ? t - it -> ss : 0)<<'\n';
		} else {
			cin>>a;
			if(st[a] == 1){
				auto it = s.lower_bound({{a, 0}, 0});
				
				int le = it -> ff.ss;
				int ri = it -> ff.ff;

				remove(it);

				if(le < a)
					s.insert({{a - 1, le}, t});
				if(ri > a)
					s.insert({{ri, a + 1}, t});
			} else {
				int ri = a;
				int le = a;
				if(st[a + 1]){
					auto it = s.lower_bound({{a, a}, 0});
					ri = it -> ff.ff;
					remove(it);
				}
				if(st[a - 1]){
					auto it = s.lower_bound({{a - 1, 0}, 0});
					le = it -> ff.ss;
					remove(it);
				}
				s.insert({{ri, le}, t});
			}
			st[a] ^= 1;
		}
	}
}

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