oj.uz

Submission #689294

# Submission time Handle Problem Language Result Execution time Memory
689294 2023-01-28T05:59:09 Z QwertyPi Street Lamps (APIO19_street_lamps) C++14
100 / 100
 1469 ms 75760 KB 
#include <bits/stdc++.h>

using namespace std;

struct BIT{
	vector<int> ip[300011], bit[300011];
	void init(){
		for(int i = 0; i < 300011; i++){
			ip[i].push_back(0); sort(ip[i].begin(), ip[i].end());
			ip[i].resize(unique(ip[i].begin(), ip[i].end()) - ip[i].begin());
			bit[i].resize(ip[i].size());
		}
	}
	void init_add(int x, int y){
		for(int i = x; i < 300011; i += i & -i){
			ip[i].push_back(y);
		}
	}
	void add(int x, int y, int v){
		for(int i = x; i < 300011; i += i & -i){
			int y2 = lower_bound(ip[i].begin(), ip[i].end(), y) - ip[i].begin();
			for(int j = y2; j < ip[i].size(); j += j & -j){
				bit[i][j] += v;
			}
		}
	}
	int qry(int x, int y){
		int ret = 0;
		for(int i = x; i; i -= i & -i){
			int y2 = upper_bound(ip[i].begin(), ip[i].end(), y) - ip[i].begin() - 1;
			for(int j = y2; j; j -= j & -j){
				ret += bit[i][j];
			}
		}
		return ret;
	}
} bit;

struct segment{
	int l, r, t;
	bool operator< (const segment& o) const {
		return l < o.l || l == o.l && r < o.r;
	}
};

vector<segment> segs[300011];

void add(const segment& s, int t2) {
	// cout << "ADD " << s.l << ' ' << s.r << ' ' << s.t << ' ' << t2 << endl;
	bit.init_add(s.l, s.r); segs[t2].push_back(s);
}

set<segment> S;
bool on[300011], isq[300011];
int L[300011], R[300011], rans[300011];

void show(){
	for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
}

void toggle(int x, int t){
	// cout << "TOGGLE " << x << ' ' << t << endl;
	if(on[x]){
		auto ptr = S.lower_bound({x, 1 << 30}); --ptr; int l = ptr->l, r = ptr->r; add(*ptr, t); S.erase(ptr);
		if(on[x - 1]) { S.insert({l, x, t}); }
		if(on[x + 1]) { S.insert({x + 1, r, t}); }
	}else{
		int l = x, r = x + 1;
		if(on[x - 1]) { auto ptr = S.lower_bound({x, -1}); --ptr; l = ptr->l; add(*ptr, t); S.erase(ptr); }
		if(on[x + 1]) { auto ptr = S.lower_bound({x, -1}); r = ptr->r; add(*ptr, t); S.erase(ptr); }
		S.insert({l, r, t});
	}
	on[x] = !on[x];
	// show();
}

void query(int l, int r, int t){
	isq[t] = true; L[t] = l, R[t] = r;
	auto ptr = S.lower_bound({l, 1 << 30}); 
	if(ptr != S.begin() && prev(ptr)->l <= l && r <= prev(ptr)->r) rans[t] += t - prev(ptr)->t;
}

void query2(int l, int r, int t){
	// cout << l << ' ' << r << ' ' << bit.qry(300010, r) << ' ' << bit.qry(l - 1, r) << endl;
	rans[t] += bit.qry(l, 300010) - bit.qry(l, r - 1);
}

int32_t main(){
	int n, q; cin >> n >> q;
	string s; cin >> s; for(int i = 1; i <= n; i++) on[i] = s[i - 1] == '1';
	vector<segment> v; 
	for(int i = 1; i <= n; i++) {
		if(on[i]){
			if(v.size() && v.back().r == i) v.back().r++; else v.push_back({i, i + 1, 0});
		}
	}
	for(auto s : v) S.insert(s);
	for(int t = 1; t <= q; t++){
		string type; cin >> type;
		if(type == "query"){
			int l, r; cin >> l >> r;
			query(l, r, t);
		}else{
			int x; cin >> x; toggle(x, t);
		}
	}
	bit.init();
	for(int t = 1; t <= q; t++){
		for(auto s : segs[t]){
			bit.add(s.l, s.r, t - s.t);
		}
		if(isq[t]){
			query2(L[t], R[t], t);
		}
	}
	for(int t = 1; t <= q; t++){
		if(isq[t]){
			cout << rans[t] << endl;
		}
	}
}

Compilation message

street_lamps.cpp: In member function 'void BIT::add(int, int, int)':
street_lamps.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |    for(int j = y2; j < ip[i].size(); j += j & -j){
      |                    ~~^~~~~~~~~~~~~~
street_lamps.cpp: In member function 'bool segment::operator<(const segment&) const':
street_lamps.cpp:42:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   42 |   return l < o.l || l == o.l && r < o.r;
      |                     ~~~~~~~~~^~~~~~~~~~
street_lamps.cpp: In function 'void show()':
street_lamps.cpp:58:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   58 |  for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
      |  ^~~
street_lamps.cpp:58:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |  for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
      |                                                                   ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 40228 KB Output is correct
2 Correct 54 ms 40124 KB Output is correct
3 Correct 53 ms 40260 KB Output is correct
4 Correct 47 ms 40140 KB Output is correct
5 Correct 47 ms 40136 KB Output is correct
6 Correct 46 ms 40164 KB Output is correct
7 Correct 49 ms 40200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 59340 KB Output is correct
2 Correct 725 ms 61880 KB Output is correct
3 Correct 850 ms 61784 KB Output is correct
4 Correct 1248 ms 69044 KB Output is correct
5 Correct 1295 ms 67144 KB Output is correct
6 Correct 1270 ms 69832 KB Output is correct
7 Correct 727 ms 51116 KB Output is correct
8 Correct 781 ms 52456 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 40396 KB Output is correct
2 Correct 50 ms 40268 KB Output is correct
3 Correct 49 ms 40284 KB Output is correct
4 Correct 49 ms 40180 KB Output is correct
5 Correct 1356 ms 73296 KB Output is correct
6 Correct 1469 ms 70756 KB Output is correct
7 Correct 1271 ms 66420 KB Output is correct
8 Correct 760 ms 52452 KB Output is correct
9 Correct 492 ms 46992 KB Output is correct
10 Correct 593 ms 47488 KB Output is correct
11 Correct 527 ms 47664 KB Output is correct
12 Correct 789 ms 51120 KB Output is correct
13 Correct 762 ms 52444 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 40264 KB Output is correct
2 Correct 60 ms 40288 KB Output is correct
3 Correct 51 ms 40268 KB Output is correct
4 Correct 51 ms 40372 KB Output is correct
5 Correct 937 ms 56920 KB Output is correct
6 Correct 1090 ms 62980 KB Output is correct
7 Correct 1170 ms 69496 KB Output is correct
8 Correct 1463 ms 75760 KB Output is correct
9 Correct 679 ms 65204 KB Output is correct
10 Correct 620 ms 70308 KB Output is correct
11 Correct 687 ms 65404 KB Output is correct
12 Correct 596 ms 70280 KB Output is correct
13 Correct 691 ms 65240 KB Output is correct
14 Correct 655 ms 70196 KB Output is correct
15 Correct 784 ms 51232 KB Output is correct
16 Correct 737 ms 52572 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 40228 KB Output is correct
2 Correct 54 ms 40124 KB Output is correct
3 Correct 53 ms 40260 KB Output is correct
4 Correct 47 ms 40140 KB Output is correct
5 Correct 47 ms 40136 KB Output is correct
6 Correct 46 ms 40164 KB Output is correct
7 Correct 49 ms 40200 KB Output is correct
8 Correct 630 ms 59340 KB Output is correct
9 Correct 725 ms 61880 KB Output is correct
10 Correct 850 ms 61784 KB Output is correct
11 Correct 1248 ms 69044 KB Output is correct
12 Correct 1295 ms 67144 KB Output is correct
13 Correct 1270 ms 69832 KB Output is correct
14 Correct 727 ms 51116 KB Output is correct
15 Correct 781 ms 52456 KB Output is correct
16 Correct 60 ms 40396 KB Output is correct
17 Correct 50 ms 40268 KB Output is correct
18 Correct 49 ms 40284 KB Output is correct
19 Correct 49 ms 40180 KB Output is correct
20 Correct 1356 ms 73296 KB Output is correct
21 Correct 1469 ms 70756 KB Output is correct
22 Correct 1271 ms 66420 KB Output is correct
23 Correct 760 ms 52452 KB Output is correct
24 Correct 492 ms 46992 KB Output is correct
25 Correct 593 ms 47488 KB Output is correct
26 Correct 527 ms 47664 KB Output is correct
27 Correct 789 ms 51120 KB Output is correct
28 Correct 762 ms 52444 KB Output is correct
29 Correct 47 ms 40264 KB Output is correct
30 Correct 60 ms 40288 KB Output is correct
31 Correct 51 ms 40268 KB Output is correct
32 Correct 51 ms 40372 KB Output is correct
33 Correct 937 ms 56920 KB Output is correct
34 Correct 1090 ms 62980 KB Output is correct
35 Correct 1170 ms 69496 KB Output is correct
36 Correct 1463 ms 75760 KB Output is correct
37 Correct 679 ms 65204 KB Output is correct
38 Correct 620 ms 70308 KB Output is correct
39 Correct 687 ms 65404 KB Output is correct
40 Correct 596 ms 70280 KB Output is correct
41 Correct 691 ms 65240 KB Output is correct
42 Correct 655 ms 70196 KB Output is correct
43 Correct 784 ms 51232 KB Output is correct
44 Correct 737 ms 52572 KB Output is correct
45 Correct 391 ms 54560 KB Output is correct
46 Correct 425 ms 54400 KB Output is correct
47 Correct 759 ms 57216 KB Output is correct
48 Correct 1260 ms 68652 KB Output is correct
49 Correct 597 ms 48128 KB Output is correct
50 Correct 604 ms 48072 KB Output is correct
51 Correct 569 ms 48208 KB Output is correct
52 Correct 614 ms 48504 KB Output is correct
53 Correct 600 ms 48600 KB Output is correct
54 Correct 691 ms 48656 KB Output is correct