Submission #545778

#	Time	Username	Problem	Language	Result	Execution time	Memory
545778		amunduzbaev	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	180 ms	1424 KiB

street_lamps

#include "bits/stdc++.h"
using namespace std;

#define int long long
#define ar array
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node{
	int y, val, sz, c, sum;
	node *lx, *rx;
	
	node(int x, int v) : val(x), sz(1), c(v), sum(v), lx(NULL), rx(NULL){
		y = uniform_int_distribution<int>(0, 2e9)(rng);
	}
};

struct rbst{
	void rec(node* a){
		a->sum = (a->lx != NULL ? a->lx->sum : 0) + (a->rx != NULL ? a->rx->sum : 0) + a->c;
	}
	node* merge(node* a, node* b){
		if(a == NULL) return b;
		if(b == NULL) return a;
		
		if(a->y > b->y){
			a->rx = merge(a->rx, b);
			rec(a);
			return a;
		} else {
			b->lx = merge(a, b->lx);
			rec(b);
			return b;
		} 
	}
	
	ar<node*, 2> split(node* a, int v){
		if(a == NULL) return {NULL, NULL};
		if(a->val < v){
			auto t = split(a->rx, v);
			a->rx = t[0]; rec(a);
			return {a, t[1]};
		} else {
			auto t = split(a->lx, v);
			a->lx = t[1]; rec(a);
			return {t[0], a};
		} 
	}
	
	bool is(node*&a, int x, int v){
		if(a == NULL) return false;
		if(a->val == x){
			a->c += v; rec(a);
			return true;
		}
		
		bool ok = 0;
		if(a->val < x) ok = is(a->rx, x, v);
		else ok = is(a->lx, x, v);
		rec(a);
		return ok;
	}
	
	void add(node*&root, int x, int v){
		if(is(root, x, v)) return;
		node* tmp = new node(x, v);
		auto tt = split(root, x);
		root = merge(tt[0], tmp);
		root = merge(root, tt[1]);
	}
	 
	int get(node*&a, int x){
		if(a == NULL) return 0;
		if(a->val <= x){
			return (a->lx != NULL ? a->lx->sum : 0) + a->c + get(a->rx, x);
		} else {
			return get(a->lx, x);
		}
	}
	
	void print(node* a){
		if(a == NULL) return;
		print(a->lx);
		cout<<a->val<<" ";
		print(a->rx);
	}
}T;

const int N = 3e5 + 5;
struct ST{
	node* tree[N << 2];
	void add(int l, int r, int L, int R, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			T.add(tree[x], L, v), T.add(tree[x], R, -v);
 			return;
		} int m = (lx + rx) >> 1;
		add(l, r, L, R, v, lx, m, x<<1), add(l, r, L, R, v, m+1, rx, x<<1|1);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		//~ cout<<"->"<<T.get(tree[x], r)[0]<<" "<<T.get(tree[x], r)[1]<<"\n";
		if(lx == rx) return T.get(tree[x], r);
		int m = (lx + rx) >> 1;
		if(l <= m) return T.get(tree[x], r) + get(l, r, lx, m, x<<1);
		else return T.get(tree[x], r) + get(l, r, m+1, rx, x<<1|1);
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q; cin>>n>>q;
	string s; cin>>s;
	set<int> ss; ss.insert(-1), ss.insert(n);
	for(int i=0;i<n;){ s[i] -= '0';
		if(!s[i]) { ss.insert(i++); continue; }
		int j = i;
		while(j<n && s[j]) j++;
		tree.add(i, j - 1, i, j, 1);
		i = j;
	}
	
	for(int t=0;t<q;t++){
		string q; cin>>q;
		if(q == "query"){
			int l, r; cin>>l>>r; l--, r-=2;
			bool is = 0;
			{
				auto it = ss.lower_bound(l);
				if(r < *it) is = 1;
			}
			
			cout<<tree.get(l, r) + is * t<<"\n";
		} else {
			int p; cin>>p; p--;
			if(s[p] == '1'){
				auto lx = --ss.upper_bound(p);
				auto rx = ss.lower_bound(p);
				tree.add(*lx + 1, p, p, *rx, t);
				ss.insert(p); s[p] = '0';
			} else {
				ss.erase(p); s[p] = '1';
				auto lx = --ss.upper_bound(p);
				auto rx = ss.lower_bound(p);
				tree.add(*lx + 1, p, p, *rx, -t);
			}
		}
	}
}

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