Submission #216616

#	Time	Username	Problem	Language	Result	Execution time	Memory
216616		theStaticMind	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3132 ms	200976 KiB

street_lamps

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;
#define rand() (rand() * rand() + rand() + 1)

vector<int> ans(300005, 0);

struct Fenwick{
	
	vector<int> bit;
	vector<ii> arr;
	int size;
	
	void modify(int j, int v){
		j++;
		for(; j < size; j += j & -j)bit[j] += v;
	}
	
	int query(int j){
		j++;
		int v = 0;
		for(; j > 0; j -= j & -j)v += bit[j];
		return v;
	}
	
	int rangequery(int a, int b){
		return query(b) - query(a - 1);
	}
	
	void rangeupdate(int a, int b, int v){
		if(a > b) return;
		modify(a, v);
		modify(b + 1, -v);
	}

	int upper(ii x){
		return upper_bound(all(arr), x) - arr.begin() - 1;
	}
	int lower(ii x){
		return lower_bound(all(arr), x) - arr.begin();
	}

	Fenwick(){}
	
	void resize(int s){
		s += 3;
		size = s;
		bit = vector<int>(s, 0);
	}
	
};

const int S = 524288;
const int size = S * 2;
Fenwick seg[size];

void update(int x1, int x2, int y1, int y2, int v, int j = 1, int l = 0, int r = S - 1){
	if(r < x1 || x2 < l) return;
	if(x1 <= l && r <= x2){
		seg[j].rangeupdate(seg[j].lower({y1, -1}), seg[j].upper({y2, 1e9}), v);
	}
	else{
		update(x1,x2,y1,y2,v,j*2,l,(l+r)/2);
		update(x1,x2,y1,y2,v,j*2+1,(l+r)/2+1,r);
	}
}
void add(int x, int y, int id){
	int j = x + S;
	while(j != 0){
		seg[j].arr.pb({y, id});
		j /= 2;
	}
}

void find(int x, int y, int id){
	int j = x + S;

	while(j != 0){
		ans[id] += seg[j].query(seg[j].lower({y, id}));
		j /= 2;
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	srand(time(NULL));

	int n, q;
	cin >> n >> q;
	string s; cin >> s;
	
	vector<bool> open(n, false);
	map<int, int> range;
	
	for(int i = 1; i <= n; i++){
		if(s[i - 1] == '1') open[i] = true;
	}
	vector<string>K(q+1);
	vector<int> L(q+1), R(q+1);

	for(int i = 1; i <= q; i++){
		cin >> K[i];
		if(K[i] == "toggle") cin >> L[i];
		else cin >> L[i] >> R[i], add(L[i], --R[i], i);

	}
	for(int i = 1; i < size; i++) sort(all(seg[i].arr)), seg[i].resize(sz(seg[i].arr));
	int last = 0;
	for(int i = 1; i <= n; i++){
		if(open[i]){
			if(!last) last = i;
		}
		else{
			if(last){
				range[last] = i - 1;
				last = 0;
			}
		}
	}
	if(last) range[last] = n;

	for(int i = 1; i <= q; i++){
		if(K[i] == "toggle"){
			int x = L[i];
			if(open[x]){
				auto itr = --range.upper_bound(x);
				int l = itr->first, r = itr->second;

				update(l, x, x, r, i);

				range.erase(itr);

				if(x != l){
					range[l] = x - 1;
				}
				if(x != r){
					range[x + 1] = r;
				}

			}
			else{
				auto itr = range.lower_bound(x);
				int l = x;
				int r = x;
				if(itr != range.end() && itr->first == x + 1){
					r = itr->second;
					range.erase(itr);
				}
				
				auto itl = range.upper_bound(x);

				if(itl != range.begin()){
					itl--;
					if(itl->second + 1 == x){
						l = itl->first;
						range.erase(itl);
					}
				}
				range[l] = r;
				update(l, x, x, r, -i);

			}
			open[x] = open[x] ^ 1;

		}
		else{
			auto itr = range.upper_bound(L[i]);
			int add = 0;
			if(itr != range.begin() && (--itr)->second >= R[i]) add = i;

			find(L[i], R[i], i);

			cout << ans[i] + add << '\n';
		}
	}
}

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