Submission #395277

#	Time	Username	Problem	Language	Result	Execution time	Memory
395277		pure_mem	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2496 ms	443252 KiB

street_lamps

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int MAXN = 3e5 + 12, INF = 1e9 + 7;

struct tree {
	int t[MAXN * 4];
	void upd(int v, int tl, int tr, int pos, int val){
		t[v] += val;
		if(tl == tr)
			return;
		int tm = (tl + tr) / 2;
		if(pos <= tm)
			upd(v * 2, tl, tm, pos, val);
		else
			upd(v * 2 + 1, tm + 1, tr, pos, val);	
	}
	int getL(int v, int tl, int tr, int pos){
		//cerr << tl << " " << tr << " " << " " << tt[v] << pos << "\n";
		if(tl == tr)
			return tl - (t[v] > 0);
		int tm = (tl + tr) / 2;
		if(pos <= tm){
			return getL(v * 2, tl, tm, pos);
		}
		else{
			int left = tm;
			if(pos <= tr || t[v * 2 + 1] != tr - tm)
				left = getL(v * 2 + 1, tm + 1, tr, pos);
			if(left == tm && t[v * 2] != tm - tl + 1)
				left = getL(v * 2, tl, tm, pos);
			else if(left ==  tm)
				left = tl - 1;
			return left;
		}
	}
	int getR(int v, int tl, int tr, int pos){
		if(tl == tr)
			return tl + (t[v] > 0);
		int tm = (tl + tr) / 2;
		if(pos > tm){
			return getR(v * 2 + 1, tm + 1, tr, pos);
		}
		else{
			int right = tm + 1;
			if(pos <= tm || t[v * 2] != tm - tl + 1)
				right = getR(v * 2, tl, tm, pos);
			if(right == tm + 1 && t[v * 2 + 1] != tr - tm)
				right = getR(v * 2 + 1, tm + 1, tr, pos);
			else if(right == tm + 1)
				right = tr + 1;
			return right;
		}
	}
}city;

struct node{
	pair<ll, int> val = MP(0LL, 0);
	node* p[2] = {nullptr, nullptr};
	node* getp(int v){
		if(!p[v])
			p[v] = new node();
		return p[v];
	}	
	void upd(int tl, int tr, int pos, ll vx, int vy){
		val.X += vx, val.Y += vy;
		if(tl == tr)
			return;
		int tm = (tl + tr) / 2;
		if(pos <= tm)
			getp(0)->upd(tl, tm, pos, vx, vy);
		else
			getp(1)->upd(tm + 1, tr, pos, vx, vy);	
	}
	pair<ll, int> get(int tl, int tr, int l, int r){
		if(tl > r || l > tr)
			return MP(0LL, 0);
		if(tl >= l && tr <= r)
			return val;
		int tm = (tl + tr) / 2;
		pair<ll, int> left = (p[0] ? p[0]->get(tl, tm, l, r): MP(0LL, 0));
		pair<ll, int> right = (p[1] ? p[1]->get(tm + 1, tr, l, r): MP(0LL, 0));
		return MP(left.X + right.X, left.Y + right.Y);
	}
};

node BIT[MAXN];

int n;
struct fenwick{
	unordered_map< int, pair<ll, int> > fw[MAXN];
	void upd(int x, int y, int vx, int vy){
		if(x > y)
			return;
		for(int i = x;i < MAXN;i |= i + 1)
			BIT[i].upd(1, n, y, vx, vy);
	}
	pair<ll, int> get(int x, int l, int r){
		ll vx = 0;
		int vy = 0;
		for(int i = x;i >= 0;i = (i & (i + 1)) - 1){
			pair<ll, int> tmp = BIT[i].get(1, n, l, r);
			//cerr << tmp.X << " " << tmp.Y << "k\n";
			vx += tmp.X, vy += tmp.Y;
		}
		return MP(vx, vy);
	}
}fw;

int answer[MAXN], q, lamp[MAXN], cntC[MAXN];

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> q;
	for(int i = 1;i <= n;i++){
		char x; 
		cin >> x, lamp[i] = (x == '1');
		if(x == '1'){
			city.upd(1, 1, n, i, 1);
			cntC[i]++;
		}
	}
	//map< pair< int, int >, int > dict;
	for(int i = 1, len = 0;i <= n + 1;i++){
		if(cntC[i])
			len++;				
		else{                
			if(len){
				//dict[MP(i - len, i - 1)] = 0;
				fw.upd(i - len, i - 1, 0, 1);
				//cerr << i - len << " " << i - 1 << "\n";
			}
			len = 0;
		}
	}
	//cerr << fw.get(2, 2, 2).Y;
	for(int i = 1;i <= q;i++){
		string tp;
		cin >> tp;
		if(tp[0] == 't'){
			int x;
			cin >> x;
			if(lamp[x]){
				int tl = city.getL(1, 1, n, x) + 1, tr = city.getR(1, 1, n, x) - 1;	
				//int val = dict[MP(tl, tr)];
				//cerr << fw.get(2, 2, 2).X << "\n";
				fw.upd(tl, tr, -i, -1), cntC[x]--;
				//cerr << fw.get(2, 2, 2).X << "\n";
				//cerr << tl << " " << tr << "\n";
				if(cntC[x] == 0)
					city.upd(1, 1, n, x, -1);
				if(cntC[x] == 0){
					if(x > 1){
						tl = city.getL(1, 1, n, x - 1) + 1, tr = x - 1;
			 			if(tl <= tr)
			 				fw.upd(tl, tr, i, 1);//, dict[MP(tl, tr)] = i;
			 		}
			 		if(x < n){
			 		    tl = x + 1, tr = city.getR(1, 1, n, x + 1) - 1;
			 			if(tl <= tr)
			 				fw.upd(tl, tr, i, 1);//, dict[MP(tl, tr)] = i;
			 		}
			 	}
			 	else{
			 		tl = city.getL(1, 1, n, x - 1) + 1, tr = (x == n ? n: city.getR(1, 1, n, x + 1) - 1);
			 		if(tl <= tr)
			 			fw.upd(tl, tr, i, 1);//, dict[MP(tl, tr)] = i;
			 	}
			 	//cerr << tl << " " << tr << "z1\n";
			}
			else{
				int tl, tr;
				cntC[x]++;
				if(cntC[x] == 1){
					if(x > 1){
						tl = city.getL(1, 1, n, x - 1) + 1, tr = x - 1;
			 			if(tl <= tr)
			 				fw.upd(tl, tr, -i, -1);//, dict[MP(tl, tr)] = i;
			 		}
			 		if(x < n){
			 		    tl = x + 1, tr = city.getR(1, 1, n, x + 1) - 1;
			 			if(tl <= tr)
			 				fw.upd(tl, tr, -i, -1);//, dict[MP(tl, tr)] = i;
			 		}
				//	cerr << fw.get(2, 2, 2).X << "\n";		
				}
				else{
					tl = city.getL(1, 1, n, x - 1) + 1, tr = (x == n ? n: city.getR(1, 1, n, x + 1) - 1);
			 		if(tl <= tr)
			 			fw.upd(tl, tr, -i, -1);
				}
				//cerr << tl << " " << tr << "x\n";
			 	if(cntC[x] == 1)
			 		city.upd(1, 1, n, x, 1);
			 	tl = city.getL(1, 1, n, x) + 1, tr = city.getR(1, 1, n, x) - 1;	
				//cerr << tl << " " << tr << " " << x << "z\n";
				fw.upd(tl, tr, i, 1);//, dict[MP(tl, tr)] = i;
				//cerr << city.getL(1, 1, n, 1) << "\n";
				//cerr << tl << " " << tr << "\n";
			}
			lamp[x] ^= 1;
		}
		else{
			int l, r;
			cin >> l >> r, r--;
			pair<ll, int> v1 = fw.get(l, r, n);
			//cerr << l << " " << r << " " << n << "\n";
			ll ans = v1.Y * 1ll * i - v1.X;
			//cerr << v1.Y << "  z  " << v1.X << "\n"; 
			cout << ans << "\n";
		}
	}
}

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