제출 #395265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395265		pure_mem	가로등 (APIO19_street_lamps)	C++14	0 / 100	2950 ms	18416 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){
		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(t[v * 2 + 1])
				left = getL(v * 2 + 1, tm + 1, tr, pos);
			if(left == tm && t[v * 2])
				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(t[v * 2])
				right = getR(v * 2, tl, tm, pos);
			if(right == tm + 1 && t[v * 2 + 1])
				right = getR(v * 2 + 1, tm + 1, tr, pos);
			else if(right == tm + 1)
				right = tr + 1;
			return right;
		}
	}
}city;

struct fenwick{
	unordered_map< int, pair<ll, int> > fw[MAXN];
	void upd(int x, int y, int vx, int vy){
		for(int i = x;i < MAXN;i |= i + 1)
			for(int j = y;j < MAXN;j |= j + 1)
				fw[i][j].X += vx, fw[i][j].Y += vy;
	}
	pair<ll, int> get(int x, int y){
		ll vx = 0;
		int vy = 0;
		for(int i = x;i >= 0;i = (i & (i + 1)) - 1){
			for(int j = y;j >= 0;j = (j & (j + 1)) - 1){
				if(fw[i].count(j))
				 	vx += fw[i][j].X, vy += fw[i][j].Y;
			}
		}
		return MP(vx, vy);
	}
}fw;

int answer[MAXN], n, 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;
		}
	}
	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)];
				fw.upd(tl, tr, i - 2 * val, -1), cntC[x]--;
				if(cntC[x] == 0)
					city.upd(1, 1, n, x, -1);
				if(cntC[x] == 0){
					tl = (x == 1 ? 0: 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;
			 	}
			 	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;
			 	}
			}
			else{
				int tl, tr;
				cntC[x]++;
				if(cntC[x] == 1){
					tl = (x == 1 ? 0: city.getL(1, 1, n, x - 1) + 1), tr = x - 1;
					if(tl <= tr)
						fw.upd(tl, tr, i - 2 * dict[MP(tl, tr)], -1);				
				}
				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 - 2 * dict[MP(tl, tr)], -1);
				}
			 	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;
			}
			lamp[x] ^= 1;
		}
		else{
			int l, r;
			cin >> l >> r, r--;
			pair<ll, int> v1 = fw.get(l, n), v2 = fw.get(l, r - 1);
			ll ans = (v1.Y - v2.Y) * 1ll * i - v1.X + v2.X;
			cout << ans << "\n";
		}
	}
}

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