oj.uz

Submission #395277

# Submission time Handle Problem Language Result Execution time Memory
395277 2021-04-28T05:30:54 Z pure_mem Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2496 ms 443252 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16844 KB Output is correct
2 Correct 12 ms 16780 KB Output is correct
3 Correct 12 ms 16844 KB Output is correct
4 Correct 12 ms 16972 KB Output is correct
5 Correct 12 ms 16940 KB Output is correct
6 Correct 12 ms 16724 KB Output is correct
7 Correct 14 ms 16776 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 17984 KB Output is correct
2 Correct 378 ms 22092 KB Output is correct
3 Correct 808 ms 33312 KB Output is correct
4 Correct 2044 ms 374244 KB Output is correct
5 Correct 1978 ms 347788 KB Output is correct
6 Correct 2090 ms 388892 KB Output is correct
7 Correct 145 ms 24496 KB Output is correct
8 Correct 180 ms 31204 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 18256 KB Output is correct
2 Correct 18 ms 18200 KB Output is correct
3 Correct 15 ms 17888 KB Output is correct
4 Correct 12 ms 16844 KB Output is correct
5 Correct 2490 ms 443252 KB Output is correct
6 Correct 2144 ms 423316 KB Output is correct
7 Correct 1520 ms 346952 KB Output is correct
8 Correct 185 ms 31156 KB Output is correct
9 Correct 98 ms 20520 KB Output is correct
10 Correct 125 ms 20924 KB Output is correct
11 Correct 109 ms 21124 KB Output is correct
12 Correct 147 ms 24388 KB Output is correct
13 Correct 184 ms 31152 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17612 KB Output is correct
2 Correct 14 ms 17940 KB Output is correct
3 Correct 15 ms 18072 KB Output is correct
4 Correct 16 ms 18252 KB Output is correct
5 Correct 584 ms 270344 KB Output is correct
6 Correct 1177 ms 338716 KB Output is correct
7 Correct 1724 ms 388292 KB Output is correct
8 Correct 2496 ms 435740 KB Output is correct
9 Correct 442 ms 21444 KB Output is correct
10 Correct 419 ms 20048 KB Output is correct
11 Correct 434 ms 21460 KB Output is correct
12 Correct 403 ms 19976 KB Output is correct
13 Correct 449 ms 21532 KB Output is correct
14 Correct 406 ms 20052 KB Output is correct
15 Correct 145 ms 24468 KB Output is correct
16 Correct 178 ms 31244 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16844 KB Output is correct
2 Correct 12 ms 16780 KB Output is correct
3 Correct 12 ms 16844 KB Output is correct
4 Correct 12 ms 16972 KB Output is correct
5 Correct 12 ms 16940 KB Output is correct
6 Correct 12 ms 16724 KB Output is correct
7 Correct 14 ms 16776 KB Output is correct
8 Correct 310 ms 17984 KB Output is correct
9 Correct 378 ms 22092 KB Output is correct
10 Correct 808 ms 33312 KB Output is correct
11 Correct 2044 ms 374244 KB Output is correct
12 Correct 1978 ms 347788 KB Output is correct
13 Correct 2090 ms 388892 KB Output is correct
14 Correct 145 ms 24496 KB Output is correct
15 Correct 180 ms 31204 KB Output is correct
16 Correct 18 ms 18256 KB Output is correct
17 Correct 18 ms 18200 KB Output is correct
18 Correct 15 ms 17888 KB Output is correct
19 Correct 12 ms 16844 KB Output is correct
20 Correct 2490 ms 443252 KB Output is correct
21 Correct 2144 ms 423316 KB Output is correct
22 Correct 1520 ms 346952 KB Output is correct
23 Correct 185 ms 31156 KB Output is correct
24 Correct 98 ms 20520 KB Output is correct
25 Correct 125 ms 20924 KB Output is correct
26 Correct 109 ms 21124 KB Output is correct
27 Correct 147 ms 24388 KB Output is correct
28 Correct 184 ms 31152 KB Output is correct
29 Correct 13 ms 17612 KB Output is correct
30 Correct 14 ms 17940 KB Output is correct
31 Correct 15 ms 18072 KB Output is correct
32 Correct 16 ms 18252 KB Output is correct
33 Correct 584 ms 270344 KB Output is correct
34 Correct 1177 ms 338716 KB Output is correct
35 Correct 1724 ms 388292 KB Output is correct
36 Correct 2496 ms 435740 KB Output is correct
37 Correct 442 ms 21444 KB Output is correct
38 Correct 419 ms 20048 KB Output is correct
39 Correct 434 ms 21460 KB Output is correct
40 Correct 403 ms 19976 KB Output is correct
41 Correct 449 ms 21532 KB Output is correct
42 Correct 406 ms 20052 KB Output is correct
43 Correct 145 ms 24468 KB Output is correct
44 Correct 178 ms 31244 KB Output is correct
45 Correct 116 ms 19204 KB Output is correct
46 Correct 190 ms 19476 KB Output is correct
47 Correct 888 ms 160456 KB Output is correct
48 Correct 1661 ms 373684 KB Output is correct
49 Correct 110 ms 20960 KB Output is correct
50 Correct 111 ms 21040 KB Output is correct
51 Correct 112 ms 21200 KB Output is correct
52 Correct 119 ms 21680 KB Output is correct
53 Correct 116 ms 21832 KB Output is correct
54 Correct 121 ms 21720 KB Output is correct