Submission #568894

#	Time	Username	Problem	Language	Result	Execution time	Memory
568894		HappyPacMan	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3679 ms	156196 KiB

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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20