oj.uz

Submission #255217

# Submission time Handle Problem Language Result Execution time Memory
255217 2020-07-31T14:46:10 Z Atalasion Street Lamps (APIO19_street_lamps) C++14
100 / 100
 1882 ms 211320 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 300000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

int koj[LOG][N], n, q, a[N], F[N], R[N];
vi seg[N << 2],fen[N << 2], L[N];
set<int> One, Zero;

bool cmp(int x, int y){
	return R[x] < R[y];
}

inline void add(int ind, int id, int x){
	for (; id < fen[ind].size(); id += id & (-id)) fen[ind][id] += x;
}

inline int get(int ind, int id){
	int res = 0;
	for (; id > 0; id -= id & (-id)) res += fen[ind][id];
	return res;
}

void build(int h, int id, int l, int r){
	if (r - l == 1){
		fen[id].pb(0);
		for (auto u:L[l]) seg[id].pb(u), fen[id].pb(0);
		sort(all(seg[id]), cmp);
		for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
  		return;
	}
	int md = (l + r) >> 1;
	build(h + 1, id << 1, l, md);
	build(h + 1, id << 1 |1 , md, r);
	fen[id].pb(0);
	for (auto u:seg[id << 1]) seg[id].pb(u), fen[id].pb(0);
	for(auto u:seg[id << 1 | 1]) seg[id].pb(u), fen[id].pb(0);
	sort(all(seg[id]), cmp);
	for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
}

void Add(int id, int lq, int rq, int x, int t, int l, int r){
	if (rq <= l || r <= lq) return;
	if (lq <= l && r <= rq){
		if (seg[id].size() == 0) return;
		int LL = 0, RR = seg[id].size();
		if (R[seg[id][0]] >= x) return;
		while (RR - LL > 1){
			int md = (LL + RR) >> 1;
			if (R[seg[id][md]] < x) LL = md;
			else RR = md;
		}
		int zar = 1;
		add(id, 1, t);
		add(id, RR + 1, -t);
		return;
	}
	int md = (l + r) >> 1;
	Add(id << 1, lq, rq, x, t, l, md);
	Add(id << 1 | 1, lq, rq, x, t, md, r);
}

void Add2(int id, int lq, int rq, int x, int t, int l, int r){
	if (rq <= l || r <= lq) return;
	if (lq <= l && r <= rq){
		if (seg[id].size() == 0) return;
		if (R[seg[id].back()] < x) return;
		int LL = -1, RR = seg[id].size() - 1;
		while (RR - LL > 1){
			int md = (RR + LL) >> 1;
			if (R[seg[id][md]] >= x) RR = md;
			else LL = md;
		}
//		cout << "Query\n";
//		cout << l << ' ' << r - 1 << ' ' << RR + 1 << ' ' << x << ' ';
		add(id, RR + 1, t);
//		cout << get(id, fen[id].size() - 1) << '\n';
		return;
	}
	int md = (l + r) >> 1;
	Add2(id << 1, lq, rq, x, t, l, md);
	Add2(id << 1 | 1, lq, rq, x, t, md, r);
}

int Get(int h, int id, int lq, int rq, int x, int l, int r){
	if (rq <= l || r <= lq)return 0;
	if (lq <= l && r <= rq){
//		cout << l << ' ' << r - 1 << ' ' << x << ' ' << koj[h][x] << ' ' << get(id, koj[h][x]) << '\n';
		return get(id, koj[h][x]);
	}
	int res = get(id, koj[h][x]);
//	cout << l << ' ' << r - 1 << ' ' << x << ' ' << koj[h][x] << ' ' <<res << '\n';
	int md = (l + r) >> 1;
	return (res + Get(h + 1, id << 1, lq, rq, x, l, md) + Get(h + 1, id << 1 | 1, lq, rq, x, md, r));
}

vector<pair<int, pii>> Q;

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	string s;
	cin >> s;
	Zero.insert(0);
	Zero.insert(n + 1);
	One.insert(0), One.insert(n + 1);
	for (int i = 1; i <= n; i++) a[i] = (s[i - 1] == '1');
	for (int i = 1; i <= n; i++){
		if (a[i] == 1) One.insert(i);
		else Zero.insert(i);
	}
	for (int i = 1; i <= q; i++){
		cin >> s;
		if (s == "query"){
			int l, r;
			cin >> l >> r;
			r--;
			R[i] = r;
			L[l].pb(i);
			Q.pb({1, {l, r}});
		}else{
			int x;
			cin >> x;
			Q.pb({2, {x, 0}});
		}
	}
	build(0, 1, 1, n + 1);
	for (int i = 1; i <= q; i++){
		auto u = Q[i - 1];
		int x = u.F;
		if (x == 1){
			int l = u.S.F, r = u.S.S;
			int res = Get(0, 1, l, l + 1, i, 1, n + 1);
			if (a[l] == 1){
				auto koj = Zero.lower_bound(l);
				if ((*koj) > r) res += i;
			} 
			cout << res << '\n';
		}else{
			int l = u.S.F;
			if (a[l] == 1){
				a[l] = 0;
				One.erase(l);
				auto koj = Zero.lower_bound(l);
				auto koj2 = koj;
				koj2--;
//				cout << (*koj2) + 1 << ' ' << l << ' ' << (*koj) << endl;
//				cout << "YES" << endl;
				Add(1, (*koj2) + 1, l + 1, (*koj), i, 1, n + 1);
//				cout << "YES2" << endl;
				Add(1, (*koj2) + 1, l + 1, l, -i, 1, n + 1);
				Zero.insert(l);
			}else{
				a[l] = 1;
				Zero.erase(l);
				auto koj = Zero.lower_bound(l);
				auto koj2 = koj;
				koj2--;
//				cout << "Fuck " << (*koj2) + 1 << ' ' << (*koj) << '\n';
				Add2(1, (*koj2) + 1, l + 1, l, -i, 1, n + 1);
				Add2(1, (*koj2) + 1, l + 1, (*koj), i, 1, n + 1);
				One.insert(l);
			
			}
		}
	}









	return 0;
}

Compilation message

street_lamps.cpp: In function 'void add(int, int, int)':
street_lamps.cpp:31:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (; id < fen[ind].size(); id += id & (-id)) fen[ind][id] += x;
         ~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void build(int, int, int, int)':
street_lamps.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
                   ~~^~~~~~~~~~~~~~~~
street_lamps.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
                  ~~^~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void Add(int, int, int, int, int, int, int)':
street_lamps.cpp:69:7: warning: unused variable 'zar' [-Wunused-variable]
   int zar = 1;
       ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 63736 KB Output is correct
2 Correct 42 ms 63916 KB Output is correct
3 Correct 50 ms 63736 KB Output is correct
4 Correct 46 ms 63864 KB Output is correct
5 Correct 38 ms 63864 KB Output is correct
6 Correct 47 ms 63864 KB Output is correct
7 Correct 38 ms 63872 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 94844 KB Output is correct
2 Correct 439 ms 100680 KB Output is correct
3 Correct 642 ms 115224 KB Output is correct
4 Correct 1294 ms 174108 KB Output is correct
5 Correct 1546 ms 179060 KB Output is correct
6 Correct 1117 ms 147828 KB Output is correct
7 Correct 1494 ms 210072 KB Output is correct
8 Correct 1379 ms 211320 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 63992 KB Output is correct
2 Correct 47 ms 64120 KB Output is correct
3 Correct 41 ms 64120 KB Output is correct
4 Correct 46 ms 64252 KB Output is correct
5 Correct 793 ms 129912 KB Output is correct
6 Correct 1276 ms 154100 KB Output is correct
7 Correct 1500 ms 175220 KB Output is correct
8 Correct 1635 ms 202484 KB Output is correct
9 Correct 340 ms 98328 KB Output is correct
10 Correct 360 ms 101896 KB Output is correct
11 Correct 347 ms 103436 KB Output is correct
12 Correct 1647 ms 200808 KB Output is correct
13 Correct 1882 ms 201712 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 64124 KB Output is correct
2 Correct 40 ms 64120 KB Output is correct
3 Correct 41 ms 64120 KB Output is correct
4 Correct 47 ms 63992 KB Output is correct
5 Correct 1686 ms 202900 KB Output is correct
6 Correct 1595 ms 176540 KB Output is correct
7 Correct 1176 ms 148208 KB Output is correct
8 Correct 796 ms 107568 KB Output is correct
9 Correct 399 ms 83216 KB Output is correct
10 Correct 277 ms 72808 KB Output is correct
11 Correct 400 ms 83392 KB Output is correct
12 Correct 281 ms 72808 KB Output is correct
13 Correct 398 ms 83440 KB Output is correct
14 Correct 280 ms 72804 KB Output is correct
15 Correct 1751 ms 203836 KB Output is correct
16 Correct 1658 ms 205232 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 63736 KB Output is correct
2 Correct 42 ms 63916 KB Output is correct
3 Correct 50 ms 63736 KB Output is correct
4 Correct 46 ms 63864 KB Output is correct
5 Correct 38 ms 63864 KB Output is correct
6 Correct 47 ms 63864 KB Output is correct
7 Correct 38 ms 63872 KB Output is correct
8 Correct 394 ms 94844 KB Output is correct
9 Correct 439 ms 100680 KB Output is correct
10 Correct 642 ms 115224 KB Output is correct
11 Correct 1294 ms 174108 KB Output is correct
12 Correct 1546 ms 179060 KB Output is correct
13 Correct 1117 ms 147828 KB Output is correct
14 Correct 1494 ms 210072 KB Output is correct
15 Correct 1379 ms 211320 KB Output is correct
16 Correct 39 ms 63992 KB Output is correct
17 Correct 47 ms 64120 KB Output is correct
18 Correct 41 ms 64120 KB Output is correct
19 Correct 46 ms 64252 KB Output is correct
20 Correct 793 ms 129912 KB Output is correct
21 Correct 1276 ms 154100 KB Output is correct
22 Correct 1500 ms 175220 KB Output is correct
23 Correct 1635 ms 202484 KB Output is correct
24 Correct 340 ms 98328 KB Output is correct
25 Correct 360 ms 101896 KB Output is correct
26 Correct 347 ms 103436 KB Output is correct
27 Correct 1647 ms 200808 KB Output is correct
28 Correct 1882 ms 201712 KB Output is correct
29 Correct 48 ms 64124 KB Output is correct
30 Correct 40 ms 64120 KB Output is correct
31 Correct 41 ms 64120 KB Output is correct
32 Correct 47 ms 63992 KB Output is correct
33 Correct 1686 ms 202900 KB Output is correct
34 Correct 1595 ms 176540 KB Output is correct
35 Correct 1176 ms 148208 KB Output is correct
36 Correct 796 ms 107568 KB Output is correct
37 Correct 399 ms 83216 KB Output is correct
38 Correct 277 ms 72808 KB Output is correct
39 Correct 400 ms 83392 KB Output is correct
40 Correct 281 ms 72808 KB Output is correct
41 Correct 398 ms 83440 KB Output is correct
42 Correct 280 ms 72804 KB Output is correct
43 Correct 1751 ms 203836 KB Output is correct
44 Correct 1658 ms 205232 KB Output is correct
45 Correct 224 ms 78256 KB Output is correct
46 Correct 307 ms 84220 KB Output is correct
47 Correct 755 ms 118692 KB Output is correct
48 Correct 1457 ms 170620 KB Output is correct
49 Correct 408 ms 108436 KB Output is correct
50 Correct 401 ms 106636 KB Output is correct
51 Correct 411 ms 108824 KB Output is correct
52 Correct 495 ms 118184 KB Output is correct
53 Correct 474 ms 118012 KB Output is correct
54 Correct 468 ms 118116 KB Output is correct