Submission #336877

#	Time	Username	Problem	Language	Result	Execution time	Memory
336877		oolimry	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1421 ms	391704 KiB

street_lamps

#include <bits/stdc++.h>
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef pair<int,int> ii;

int n, Q, SZ; 

struct query{
	int l, r, t, ans;
	bool operator< (const query &Q){
		return this->r > Q.r;
	}
};
struct update{
	int l, r, t;
	bool operator< (const update &U){
		return this->r > U.r;
	}
};

namespace fenwick{
	int n = 300005;
	int tree[300007];
	vector<ii> toundo;
	void update(int i, int v, bool undo = false){
		if(!undo) toundo.push_back(ii(i,v));
		for(;i <= n;i += i&(-i)) tree[i] += v;
	}
	int query(int i){
		int ans = 0;
		for(;i > 0;i -= i&(-i)) ans += tree[i];
		return ans;
	}
	void undo(){
		for(ii B : toundo) update(B.first, -B.second, true);
		toundo.clear();
	}
};


set<ii> pairs;

vector<int> leafs;
vector<query> queries[600006];
vector<update> updates[600006];

void makeupdate(int l, int r, int t, bool add){
	if(add){
		pairs.insert(ii(l,r));
		updates[leafs[t]].push_back({l,r,-t});
	}
	else{
		pairs.erase(ii(l,r));
		updates[leafs[t]].push_back({l,r,t});
	}
}

void makequery(int l, int r, int t){
	auto it = pairs.upper_bound(ii(l,1e9));
	int ans = 0;
	
	if(it != pairs.begin()){
		it--;
		if(it->first <= l && r <= it->second) ans = t;
	}
	
	queries[leafs[t]].push_back({l, r, t, ans}); 
}

void dfs(int u){
	if(u >= 2*SZ) return;
	if(u >= SZ) leafs.push_back(u);
	dfs(u<<1); dfs(u<<1|1);
}

int arr[300005];
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> Q; SZ = Q+1;
	
	string original; cin >> original;
	for(int i = 1;i <= n;i++) arr[i] = original[i-1] - '0';
	
	
	int l = -1;
	for(int i = 1;i <= n;i++){
		if(arr[i] == 1 && l == -1) l = i;
		if(arr[i] == 1 && arr[i+1] == 0){
			pairs.insert(ii(l,i));
			l = -1;
		}
	}
	
	for(int i = 1;i <= n;i++) assert(fenwick::tree[i] == 0);
	dfs(1);
	
	for(int t = 1;t <= Q;t++){
		string s; cin >> s;
		
		if(s[0] == 't'){
			int x; cin >> x;
			if(arr[x] == 0){ ///turn on
				makeupdate(x,x,t,true);
				if(arr[x-1] == 1){
					auto it = pairs.lower_bound(ii(x,-1));
					auto pre = prev(it);
					
					makeupdate(pre->first, it->second, t, true);
					makeupdate(pre->first, pre->second, t, false);
					makeupdate(it->first, it->second, t, false);
				}
				if(arr[x+1] == 1){
					auto nxt = pairs.upper_bound(ii(x,1e9));
					auto it = prev(nxt);
					
					makeupdate(it->first, nxt->second, t, true);
					makeupdate(nxt->first, nxt->second, t, false);
					makeupdate(it->first, it->second, t, false);
				}
				arr[x] = 1;
			}
			else{
				auto it = --pairs.upper_bound(ii(x,1e9));
				
				if(it->first != x) makeupdate(it->first, x-1, t, true); // pairs.insert(ii(it->first,x-1));
				if(it->second != x) makeupdate(x+1, it->second, t, true);
				
				pairs.erase(it);
				makeupdate(it->first, it->second, t, false);
				
				arr[x] = 0;
			}
		}
		else{
			int l, r; cin >> l >> r;
			makequery(l, r-1, t);
		}
	}
			
	for(int node = SZ;node < 2*SZ;node++){
		sort(all(queries[node]));
		sort(all(updates[node]));
	}
		
	for(int node = SZ-1;node >= 1;node--){
		int LC = node<<1, RC = node<<1|1;
		
		auto it = updates[LC].begin();
		
		for(query &q : queries[RC]){
			while(it != updates[LC].end()){
				if(it->r < q.r) break;
				else{
					fenwick::update(it->l, it->t);
					it++;
				}
			}
			q.ans += fenwick::query(q.l);
		}
		
		fenwick::undo();
		
		merge(all(queries[LC]), all(queries[RC]), back_inserter(queries[node]));
		merge(all(updates[LC]), all(updates[RC]), back_inserter(updates[node]));
	}
	
	sort(all(queries[1]), [&](query a, query b){ return a.t < b.t; });
	for(query q : queries[1]) cout << q.ans << "\n";
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20