Submission #568894

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
568894	2022-05-26T10:12:09 Z	HappyPacMan	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3679 ms	156196 KB

street_lamps

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 2;
vector<int> ord[4*maxn],bit[4*maxn];

// order preprocessing
void updOrd(int i,int l,int r,int u,int v){
	if(l == r){
		ord[i].emplace_back(v);
	}else{
		int m = (l+r)/2;
		ord[i].emplace_back(v);
		if(u <= m){
			updOrd(i<<1,l,m,u,v);
		}else{
			updOrd(i<<1|1,m+1,r,u,v);
		}
	}
}

// Binary Indexed Tree on Segment Tree
void BitUpd(int t,int u,int v){
	for(++u;u<=bit[t].size();u+=u&(-u)){
		bit[t][u-1] += v;
	}
}
int BitQry(int t,int u){
	int res = 0;
	for(++u;u>0;u-=u&(-u)){
		res += bit[t][u-1];
	}
	return res;
}

void SegUpd(int i,int l,int r,int u,int v,int w){
	int idx = lower_bound(ord[i].begin(),ord[i].end(),v)-ord[i].begin();
	if(l == r){
		BitUpd(i,idx,w);
	}else{
		int m = (l+r)/2;
		BitUpd(i,idx,w);
		if(u <= m){
			SegUpd(i<<1,l,m,u,v,w);
		}else{
			SegUpd(i<<1|1,m+1,r,u,v,w);
		}
	}
}
int SegQry(int i,int l,int r,int ql,int qr,int v){
	int idx = upper_bound(ord[i].begin(),ord[i].end(),v)-ord[i].begin()-1;
	if(l > qr || r < ql){
		return 0;
	}else if(ql <= l && r <= qr){
		return BitQry(i,idx);
	}else{
		int m = (l+r)/2;
		return SegQry(i<<1,l,m,ql,qr,v)+SegQry(i<<1|1,m+1,r,ql,qr,v);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N,Q;
	string S;
	cin >> N >> Q >> S;
	set<pair<int,int> > range;
	int start = 0;
	for(int i=0;i<N;i++){
		if(S[i] == '0'){
			if(start != i){
				range.emplace(start,i-1);
				updOrd(1,0,N-1,i-1,start);
			}
			start = i+1;
		}
	}
	if(start != N){
		range.emplace(start,N-1);
		updOrd(1,0,N-1,N-1,start);
	}
	vector<pair<int,int> > query;
	while(Q--){
		string tp;
		cin >> tp;
		// toggle tested
		if(tp == "toggle"){
			int i;
			cin >> i;
			query.emplace_back(i,-1);
			if(range.upper_bound(make_pair(i,-1)) == range.begin() || (*prev(range.upper_bound(make_pair(i,-1)))).second < i-1){
				int li = i-1, ri = i-1;
				if(range.upper_bound(make_pair(i,-1)) != range.begin() && (*prev(range.upper_bound(make_pair(i,-1)))).second == i-2){
					li = (*prev(range.upper_bound(make_pair(i,-1)))).first;
					range.erase(prev(range.upper_bound(make_pair(i,-1))));
				}
				if(range.upper_bound(make_pair(i,-1)) != range.end() && (*range.upper_bound(make_pair(i,-1))).first == i){
					ri = (*range.upper_bound(make_pair(i,-1))).second;
					range.erase(range.upper_bound(make_pair(i,-1)));
				}
				updOrd(1,0,N-1,ri,li);
				range.emplace(li,ri);
			}else{
				auto [li,ri] = *prev(range.upper_bound(make_pair(i,-1)));
				range.erase(prev(range.upper_bound(make_pair(i,-1))));
				if(li < i-1){
					range.emplace(li,i-2);
					updOrd(1,0,N-1,i-2,li);
				}
				if(ri > i-1){
					range.emplace(i,ri);
					updOrd(1,0,N-1,ri,i);
				}
			}
		}else{
			int a,b;
			cin >> a >> b;
			query.emplace_back(a,b);
		}
	}
	for(int i=0;i<4*maxn;i++){
		sort(ord[i].begin(),ord[i].end());
		ord[i].erase(unique(ord[i].begin(),ord[i].end()),ord[i].end());
		bit[i].resize(ord[i].size(),0);
	}
	range.clear();
	map<pair<int,int>,int> lastIdx;
	start = 0;
	for(int i=0;i<N;i++){
		if(S[i] == '0'){
			if(start != i){
				range.emplace(start,i-1);
				lastIdx[make_pair(start,i-1)] = 0;
			}
			start = i+1;
		}
	}
	if(start != N){
		range.emplace(start,N-1);
		lastIdx[make_pair(start,N-1)] = 0;
	}
	int curIdx = 1;
	for(auto [i,j] : query){
		if(j == -1){
			if(range.upper_bound(make_pair(i,-1)) == range.begin() || (*prev(range.upper_bound(make_pair(i,-1)))).second < i-1){
				int li = i-1, ri = i-1;
				if(range.upper_bound(make_pair(i,-1)) != range.begin() && (*prev(range.upper_bound(make_pair(i,-1)))).second == i-2){
					li = (*prev(range.upper_bound(make_pair(i,-1)))).first;
					auto [lj,rj] = *prev(range.upper_bound(make_pair(i,-1)));
					SegUpd(1,0,N-1,rj,lj,curIdx-lastIdx[make_pair(lj,rj)]);
					range.erase(prev(range.upper_bound(make_pair(i,-1))));
				}
				if(range.upper_bound(make_pair(i,-1)) != range.end() && (*range.upper_bound(make_pair(i,-1))).first == i){
					ri = (*range.upper_bound(make_pair(i,-1))).second;
					auto [lj,rj] = *range.upper_bound(make_pair(i,-1));
					SegUpd(1,0,N-1,rj,lj,curIdx-lastIdx[make_pair(lj,rj)]);
					range.erase(range.upper_bound(make_pair(i,-1)));
				}
				lastIdx[make_pair(li,ri)] = curIdx;
				range.emplace(li,ri);
			}else{
				auto [li,ri] = *prev(range.upper_bound(make_pair(i,-1)));
				range.erase(prev(range.upper_bound(make_pair(i,-1))));
				SegUpd(1,0,N-1,ri,li,curIdx-lastIdx[make_pair(li,ri)]);
				if(li < i-1){
					lastIdx[make_pair(li,i-2)] = curIdx;
					range.emplace(li,i-2);
				}
				if(ri > i-1){
					lastIdx[make_pair(i,ri)] = curIdx;
					range.emplace(i,ri);
				}
			}
		}else{
			int res = SegQry(1,0,N-1,j-2,N-1,i-1);
			if(range.upper_bound(make_pair(i,-1)) != range.begin() && (*prev(range.upper_bound(make_pair(i,-1)))).second >= j-2){
				auto [lj,rj] = *prev(range.upper_bound(make_pair(i,-1)));;
				res += curIdx-lastIdx[make_pair(lj,rj)];
			}
			cout << res << '\n';
		}
		curIdx++;
	}
}

Compilation message

street_lamps.cpp: In function 'void BitUpd(int, int, int)':
street_lamps.cpp:23:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(++u;u<=bit[t].size();u+=u&(-u)){
      |          ~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:105:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |     auto [li,ri] = *prev(range.upper_bound(make_pair(i,-1)));
      |          ^
street_lamps.cpp:144:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  144 |  for(auto [i,j] : query){
      |           ^
street_lamps.cpp:150:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  150 |      auto [lj,rj] = *prev(range.upper_bound(make_pair(i,-1)));
      |           ^
street_lamps.cpp:156:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  156 |      auto [lj,rj] = *range.upper_bound(make_pair(i,-1));
      |           ^
street_lamps.cpp:163:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  163 |     auto [li,ri] = *prev(range.upper_bound(make_pair(i,-1)));
      |          ^
street_lamps.cpp:178:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  178 |     auto [lj,rj] = *prev(range.upper_bound(make_pair(i,-1)));;
      |          ^

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	56660 KB	Output is correct
2	Correct	33 ms	56660 KB	Output is correct
3	Correct	36 ms	56668 KB	Output is correct
4	Correct	36 ms	56560 KB	Output is correct
5	Correct	36 ms	56652 KB	Output is correct
6	Correct	34 ms	56660 KB	Output is correct
7	Correct	39 ms	56592 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	445 ms	67152 KB	Output is correct
2	Correct	546 ms	68028 KB	Output is correct
3	Correct	1038 ms	74360 KB	Output is correct
4	Correct	3012 ms	125004 KB	Output is correct
5	Correct	2918 ms	116784 KB	Output is correct
6	Correct	3288 ms	130680 KB	Output is correct
7	Correct	242 ms	61540 KB	Output is correct
8	Correct	229 ms	61776 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	56916 KB	Output is correct
2	Correct	36 ms	56788 KB	Output is correct
3	Correct	35 ms	56768 KB	Output is correct
4	Correct	34 ms	56588 KB	Output is correct
5	Correct	3382 ms	145620 KB	Output is correct
6	Correct	2983 ms	139740 KB	Output is correct
7	Correct	2307 ms	116144 KB	Output is correct
8	Correct	220 ms	61776 KB	Output is correct
9	Correct	125 ms	59584 KB	Output is correct
10	Correct	129 ms	60988 KB	Output is correct
11	Correct	132 ms	61032 KB	Output is correct
12	Correct	197 ms	61360 KB	Output is correct
13	Correct	216 ms	61604 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	56780 KB	Output is correct
2	Correct	33 ms	56848 KB	Output is correct
3	Correct	39 ms	56884 KB	Output is correct
4	Correct	35 ms	56916 KB	Output is correct
5	Correct	988 ms	102544 KB	Output is correct
6	Correct	1847 ms	121068 KB	Output is correct
7	Correct	2591 ms	134976 KB	Output is correct
8	Correct	3679 ms	156196 KB	Output is correct
9	Correct	591 ms	74716 KB	Output is correct
10	Correct	503 ms	74700 KB	Output is correct
11	Correct	570 ms	74712 KB	Output is correct
12	Correct	496 ms	74892 KB	Output is correct
13	Correct	592 ms	74700 KB	Output is correct
14	Correct	499 ms	74884 KB	Output is correct
15	Correct	215 ms	66768 KB	Output is correct
16	Correct	232 ms	67532 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	56660 KB	Output is correct
2	Correct	33 ms	56660 KB	Output is correct
3	Correct	36 ms	56668 KB	Output is correct
4	Correct	36 ms	56560 KB	Output is correct
5	Correct	36 ms	56652 KB	Output is correct
6	Correct	34 ms	56660 KB	Output is correct
7	Correct	39 ms	56592 KB	Output is correct
8	Correct	445 ms	67152 KB	Output is correct
9	Correct	546 ms	68028 KB	Output is correct
10	Correct	1038 ms	74360 KB	Output is correct
11	Correct	3012 ms	125004 KB	Output is correct
12	Correct	2918 ms	116784 KB	Output is correct
13	Correct	3288 ms	130680 KB	Output is correct
14	Correct	242 ms	61540 KB	Output is correct
15	Correct	229 ms	61776 KB	Output is correct
16	Correct	37 ms	56916 KB	Output is correct
17	Correct	36 ms	56788 KB	Output is correct
18	Correct	35 ms	56768 KB	Output is correct
19	Correct	34 ms	56588 KB	Output is correct
20	Correct	3382 ms	145620 KB	Output is correct
21	Correct	2983 ms	139740 KB	Output is correct
22	Correct	2307 ms	116144 KB	Output is correct
23	Correct	220 ms	61776 KB	Output is correct
24	Correct	125 ms	59584 KB	Output is correct
25	Correct	129 ms	60988 KB	Output is correct
26	Correct	132 ms	61032 KB	Output is correct
27	Correct	197 ms	61360 KB	Output is correct
28	Correct	216 ms	61604 KB	Output is correct
29	Correct	31 ms	56780 KB	Output is correct
30	Correct	33 ms	56848 KB	Output is correct
31	Correct	39 ms	56884 KB	Output is correct
32	Correct	35 ms	56916 KB	Output is correct
33	Correct	988 ms	102544 KB	Output is correct
34	Correct	1847 ms	121068 KB	Output is correct
35	Correct	2591 ms	134976 KB	Output is correct
36	Correct	3679 ms	156196 KB	Output is correct
37	Correct	591 ms	74716 KB	Output is correct
38	Correct	503 ms	74700 KB	Output is correct
39	Correct	570 ms	74712 KB	Output is correct
40	Correct	496 ms	74892 KB	Output is correct
41	Correct	592 ms	74700 KB	Output is correct
42	Correct	499 ms	74884 KB	Output is correct
43	Correct	215 ms	66768 KB	Output is correct
44	Correct	232 ms	67532 KB	Output is correct
45	Correct	141 ms	62856 KB	Output is correct
46	Correct	263 ms	64616 KB	Output is correct
47	Correct	1308 ms	90628 KB	Output is correct
48	Correct	2734 ms	129532 KB	Output is correct
49	Correct	160 ms	64040 KB	Output is correct
50	Correct	189 ms	64072 KB	Output is correct
51	Correct	207 ms	64228 KB	Output is correct
52	Correct	188 ms	64568 KB	Output is correct
53	Correct	182 ms	64576 KB	Output is correct
54	Correct	164 ms	64536 KB	Output is correct