Submission #545657

#	Time	Username	Problem	Language	Result	Execution time	Memory
545657		amunduzbaev	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	2240 ms	197452 KiB

street_lamps

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

#define int long long

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

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

struct rbst{
	void push(node* a){
		if(a == NULL) return;
		if(a->lx != NULL){
			a->lx->sum += a->p;
			a->lx->p += a->p;
		} if(a->rx != NULL){
			a->rx->sum += a->p;
			a->rx->p += a->p;
		} a->p = 0;
	}
	
	node* merge(node* a, node* b){
		push(a); push(b);
		if(a == NULL) return b;
		if(b == NULL) return a;
		
		if(a->y > b->y){
			a->rx = merge(a->rx, b);
			return a;
		} else {
			b->lx = merge(a, b->lx);
			return b;
		}
	}
	
	ar<node*, 2> split(node* a, int v){
		if(a == NULL) return {NULL, NULL};
		push(a);
		if(a->val < v){
			auto t = split(a->rx, v);
			a->rx = t[0]; 
			return {a, t[1]};
		} else {
			auto t = split(a->lx, v);
			a->lx = t[1];
			return {t[0], a};
		}
	}
	
	bool is(node* a, int x){
		push(a);
		if(a == NULL) return false;
		if(a->val == x) return true;
		if(a->val < x) return is(a->rx, x);
		else return is(a->lx, x);
	}
	
	void add(node*&root, int x){
		if(is(root, x)) return;
		node* tmp = new node(x);
		auto tt = split(root, x);
		root = merge(tt[0], tmp);
		root = merge(root, tt[1]);
	}
	
	ar<int, 2> get(node* a, int x){
		push(a);
		if(a == NULL) return {-1, 0};
		if(a->val <= x){
			return max((ar<int, 2>){a->val, a->sum}, 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), T.add(tree[x], R);
			auto t1 = T.split(tree[x], L);
			auto t2 = T.split(t1[1], R);
			//~ T.print(t1[0]);
			//~ cout<<endl;
			//~ T.print(t2[0]);
			//~ cout<<endl;
			//~ T.print(t2[1]);
			//~ cout<<endl;
			t2[0]->sum += v, t2[0]->p += v;
			tree[x] = T.merge(t1[0], t2[0]);
			tree[x] = T.merge(tree[x], t2[1]);
			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)[1];
		int m = (lx + rx) >> 1;
		if(l <= m) return T.get(tree[x], r)[1] + get(l, r, lx, m, x<<1);
		else return T.get(tree[x], r)[1] + 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;){
		if(s[i] == '0') { ss.insert(i++); continue; }
		int j = i;
		while(j<n && s[j] == '1') j++;
		int l = i;
		while(i<j){
			//~ cout<<l<<" "<<i<<" ";
			//~ cout<<i<<" "<<j<<"\n";
			tree.add(l, i, i, j, 1);
			i++;
		}
	}
	
	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);
				//~ (*lx) + 1, (*rx) - 1
				tree.add(*lx + 1, p, p, *rx, t);
				ss.insert(p); s[p] = '0';
			} else {
				ss.erase(p);
				auto lx = --ss.upper_bound(p);
				auto rx = ss.lower_bound(p);
				tree.add(*lx + 1, p, p, *rx, -t);
				s[p] = '1';
			}
		}
	}
}

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