Submission #216598

#	Time	Username	Problem	Language	Result	Execution time	Memory
216598		theStaticMind	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	5078 ms	189460 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 Node{
	int left, right;
	int key, prior;
	int id, lazy;

	Node(){
		left = right = key = prior = id = lazy = 0;
	}

	bool operator<(Node& b){
		return key < b.key || (key == b.key && id < b.id);
	}
} node[7000000];

int new_node(int k = 0, int i = 0){
	static int ind = 1; assert(ind < 7000000);
	node[ind].key = k;
	node[ind].id = i;
	node[ind].prior = rand();
	return ind++;
}

struct Treap{
	int root = 0;

	void push(int j){
		if(!j) return;

		int l = node[j].left;
		int r = node[j].right;

		int& z = node[j].lazy;

		ans[node[j].id] += z;
		if(l) node[l].lazy += z;
		if(r) node[r].lazy += z;
		z = 0;

	}

	void split(int j, Node& v, int& l, int& r){
		push(j);
		if(!j) l = r = 0;
		else if(node[j] < v) split(node[j].right, v, node[j].right, r), l = j;
		else split(node[j].left, v, l, node[j].left), r = j;
	}
	void merge(int& j, int l, int r){
		push(l), push(r);
		if(!l || !r) j = max(l, r);
		else if(node[l].prior > node[r].prior) merge(node[l].right, node[l].right, r), j = l;
		else merge(node[r].left, l, node[r].left), j = r;
	}
	void insert(int& j, int i){
		push(j);
		if(!j) j = i;
		else if(node[i].prior < node[j].prior){
			if(node[i] < node[j]) insert(node[j].left, i);
			else insert(node[j].right, i);
		}
		else split(j, node[i], node[i].left, node[i].right), j = i;
	}
	void add(int k, int id){
		insert(root, new_node(k, id));
	}

	void update(int y1, int y2, int v){
		int a, b, c;
		Node temp1, temp2;
		temp1.key = y1;
		temp1.id = -1e9;
		temp2.key = y2;
		temp2.id = 1e9;
		
		split(root, temp1, a, b);
		split(b, temp2, b, c);
		
		node[b].lazy += v;
		
		merge(root, a, b);
		merge(root, root, c);
	}
	int find(int j, Node& c){
		push(j);
		if(node[j].id == c.id)return j;
		if(c < node[j]) return find(node[j].left, c);
		else return find(node[j].right, c);
	}
};

const int S = 524288;
const int size = S * 2;
Treap 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].update(y1, y2, 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].add(y, id);
		j /= 2;
	}
}

void find(int x, int y, int id){
	int j = x + S;
	Node c;
	c.key = y;
	c.id = id;
	while(j != 0){
		seg[j].find(seg[j].root, c);
		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);

	}

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