oj.uz

Submission #224791

# Submission time Handle Problem Language Result Execution time Memory
224791 2020-04-18T19:50:49 Z AQT Street Lamps (APIO19_street_lamps) C++14
20 / 100
 724 ms 49684 KB 
// 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;
	vector<int> vec;
	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;
			vec.push_back(n);
			n += n&-n;
		}
	}
	void clr(){
		//cout << "c: " << n << endl;
		for(int n : vec){
			bit[n] = 0;
		}
		vec.clear();
	}
};

int N, Q;
bool state[300005];
set<int> st;
set<pair<pair<int, int>, int>> rng;
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 << "bling: " << q.second << endl;
			//cout << crnt << 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);
		}
	}
	bit.clr();
	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

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:59:16: warning: variable 'valk' set but not used [-Wunused-but-set-variable]
  int crnt = 0, valk = 0;
                ^~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 207 ms 31764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 614 ms 43008 KB Output is correct
6 Correct 724 ms 49684 KB Output is correct
7 Correct 645 ms 47192 KB Output is correct
8 Correct 331 ms 31712 KB Output is correct
9 Correct 106 ms 21856 KB Output is correct
10 Correct 111 ms 24412 KB Output is correct
11 Correct 117 ms 24416 KB Output is correct
12 Correct 398 ms 45784 KB Output is correct
13 Correct 329 ms 32152 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Incorrect 6 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -