Submission #224786

#	Time	Username	Problem	Language	Result	Execution time	Memory
224786		AQT	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	5082 ms	45324 KiB

street_lamps

// Problem : APIO '19 P3 - Street Lamps
// Contest : DMOJ
// URL : https://dmoj.ca/problem/apio19p3
// Memory Limit : 512 MB
// Time Limit : 2500 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

using namespace std;

struct FenwickTree{
	int bit[300005];
	int lim;
	int query(int n){
		//cout << "q: " << n << endl;
		int ret = 0;
		while(n){
			ret += bit[n];
			n -= n&-n;
		}
		return ret;
	}
	void add(int n, int v){
		//cout << "a: " << n << endl;
		while(n <= lim){
			bit[n] += v;
			n += n&-n;
		}
	}
	void clr(int n){
		//cout << "c: " << n << endl;
		while(n <= lim){
			bit[n] = 0;
			n += n&-n;
		}
	}
};

int N, Q;
bool state[300005];
set<int> st;
vector<pair<pair<int, int>, int>> upd, qu;
int ans[300005];
FenwickTree bit;

void solve(int l, int r, vector<pair<pair<int, int>, int>> upd, vector<pair<pair<int, int>, int>> qu){
	if(l > r){
		return;
	}
	//cout << l << " " << r << endl;
	int mid = (l+r)>>1;
	vector<pair<pair<int, int>, int>> lftu, rhtu, lftq, rhtq;
	int idx = 0;
	int crnt = 0, valk = 0;
	for(auto q : qu){
		while(idx < (int) upd.size() && abs(upd[idx].second) > q.second){
			if(upd[idx].first.first <= mid){
				if(upd[idx].first.second >= mid){
					//cout << upd[idx].second << endl;
					bit.add(1, upd[idx].second);
					bit.add(upd[idx].first.second+1, -upd[idx].second);
					if(upd[idx].second > 0){
						valk = upd[idx].second;
						crnt = upd[idx].first.second;
					}
					else{
						valk = 0;
						crnt = 0;
					}
				}
				lftu.push_back(upd[idx]);
			}
			else{
				rhtu.push_back(upd[idx]);
			}
			idx++;
		}
		if(q.first.first >= mid){
			//cout << q.second << endl;
			if(crnt >= q.first.second){
				//cout << "hi" << endl;
				ans[q.second] -= q.second;
			}
			ans[q.second] += bit.query(q.first.second);
			if(q.first.first > mid){
				rhtq.push_back(q);
			}
		}
		else{
			lftq.push_back(q);
		}
	}
	for(int i = 1; i<=N; i++){
		bit.clr(i);
	}
	solve(l, mid-1, lftu, lftq);
	solve(mid+1, r, rhtu, rhtq);
}

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> Q;
	st.insert(0);
	st.insert(N+1);
	for(int i = 1; i<=N; i++){
		char c;
		cin >> c;
		state[i] = (c == '1');
		if(!state[i]){
			st.insert(i);
		}
	}
	for(int i = 1; i<=N; i++){
		if(state[i]){
			int idx = *st.lower_bound(i);
			idx--;
			upd.push_back({{i, idx}, Q+1});
			i = idx;
		}
	}
	for(int q = Q; q; q--){
		string s;
		cin >> s;
		if(s == "query"){
			int l, r;
			cin >> l >> r;
			r--;
			qu.push_back({{l, r}, q});
		}
		else{
			int i;
			cin >> i;
			state[i] ^= 1;
			const int coe = state[i] ? 1 : -1;
			int r = i, l = i;
			if(state[i]){
				st.erase(i);
			}
			if(state[i+1]){
				r = *st.lower_bound(i)-1;
				upd.push_back({{i+1, r}, -coe*q});
			}
			if(state[i-1]){
				l = *(--st.lower_bound(i))+1;
				upd.push_back({{l, i-1}, -coe*q});
			}
			upd.push_back({{l, r}, coe*q});			
			if(!state[i]){
				st.insert(i);
			}
			ans[q] = -1;
		}
	}
	bit.lim = N;
	solve(1, N, upd, qu);
	/*
	for(auto q : upd){
		cout << q.first.first << " " << q.first.second << " " << q.second << "\n";
	}
	*/
	for(int q = Q; q; q--){
		if(ans[q] != -1){
			cout << ans[q] << "\n";
		}
	}
}

Compilation message (stderr)

street_lamps.cpp: In function 'void solve(int, int, std::vector<std::pair<std::pair<int, int>, int> >, std::vector<std::pair<std::pair<int, int>, int> >)':
street_lamps.cpp:56:16: warning: variable 'valk' set but not used [-Wunused-but-set-variable]
  int crnt = 0, valk = 0;
                ^~~~

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