Submission #1182601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182601		epicci23	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	1415 ms	450180 KiB

street_lamps

#pragma GCC optimization("O3 , unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int N = 3e5 + 7;
const int inf = 1e9 + 7;
int n,q;
struct SEGT{
	struct Node{
		int left , right , val;
		Node():left(-1) , right(-1) , val(0){}
	};
	vector < Node > tree;
	SEGT():tree(vector<Node>(1)){}
	int query(int qp , int ind=0 , int l=0 , int r=N){
		if(l == r){
			return tree[ind].val;
		}
		int mid = (l + r) / 2;
		if(qp <= mid){
			if(tree[ind].left == -1){
				tree[ind].left = sz(tree);
				tree.push_back(Node());
			}
			return tree[ind].val + query(qp,tree[ind].left,l,mid);
		}
		else{
			if(tree[ind].right == -1){
				tree[ind].right = sz(tree);
				tree.push_back(Node());
			}
			return tree[ind].val + query(qp,tree[ind].right,mid+1,r);
		}
	}
	void update(int ql , int qr , int qval , int ind=0 , int l=0 , int r=N){
		if(l >= ql and r <= qr){
			tree[ind].val += qval;
			return;
		}
		else if(l > qr or r < ql){
			return;
		}
		else{
			int mid = (l + r) / 2;
			if(tree[ind].left == -1){
				tree[ind].left = sz(tree);
				tree.push_back(Node());
			}
			if(tree[ind].right == -1){
				tree[ind].right = sz(tree);
				tree.push_back(Node());
			}
			update(ql , qr , qval , tree[ind].left , l , mid);
			update(ql , qr , qval , tree[ind].right , mid+1 , r);
		}
	}
};
SEGT fen[N];
void update(int a , int b , int val){
	while(a < N){
		fen[a].update(a,b,val);
		a += a & (-a);
	}
	b++;
	while(b < N){
		fen[b].update(a,b,-val);
		b += b & (-b);
	}
}
int query(int p1 , int p2){
	int ret = 0;
	while(p1 > 0){
		ret += fen[p1].query(p2);
		p1 -= p1 & (-p1);
	}
	return ret;
}
void solve(){
	cin >> n >> q;
	string str;
	cin >> str;
	set < array < int , 3 > > ste;
	int lst = 0;
	for(int i = 0;i<=n;i++){
		if(i == n or str[i] == '0'){
			if(lst <= (i-1))ste.insert({lst+1 , i , 0});
			lst = i+1;
		}
	}
	for(int ttime = 1;ttime<=q;ttime++){
		// cerr << "str : " << str << endl;
		// cerr << "ste : ";for(auto itr : ste)cerr << itr[0] << "," << itr[1] << "," << itr[2] << "   ";cerr << endl;
		string typ;
		cin >> typ;
		if(typ == "toggle"){
			int p;
			cin >> p;
			// cerr << "QUERY : " << typ << " " << p << endl;
			if(str[p-1] == '0'){
				auto bfr = ste.lower_bound({p , 0 , 0});
				auto nxt = ste.lower_bound({p , 0 , 0});
				if(bfr != ste.begin() and nxt != ste.end()){
					--bfr;
					auto pai1 = *bfr;
					auto pai2 = *nxt;
					if(pai1[1] == p-1 and pai2[0] == p+1){
						update(pai1[0] , pai1[1] , ttime - pai1[2]);
						ste.erase(bfr);

						update(pai2[0] , pai2[1] , ttime - pai2[2]);
						ste.erase(nxt);

						ste.insert({pai1[0] , pai2[1] , ttime});	
					}
					else if(pai1[1] == p-1){
						update(pai1[0] , pai1[1] , ttime - pai1[2]);
						ste.erase(bfr);
						ste.insert({pai1[0] , pai1[1]+1 , ttime});	
					}
					else if(pai2[0] == p+1){
						update(pai2[0] , pai2[1] , ttime - pai2[2]);
						ste.erase(nxt);
						ste.insert({pai2[0]-1 , pai2[1] , ttime});	
					}
					else{
						ste.insert({p , p , ttime});
					}
				}
				else if(bfr != ste.begin()){
					--bfr;
					auto pai1 = *bfr;
					if(pai1[1] == p-1){
						update(pai1[0] , pai1[1] , ttime - pai1[2]);
						ste.erase(bfr);
						ste.insert({pai1[0] , pai1[1]+1 , ttime});
					}
					else{
						ste.insert({p , p , ttime});
					}
				}
				else if(nxt != ste.end()){
					auto pai2 = *nxt;
					if(pai2[0] == p+1){
						update(pai2[0] , pai2[1] , ttime - pai2[2]);
						ste.erase(nxt);
						ste.insert({pai2[0]-1 , pai2[1] , ttime});
					}
					else{
						ste.insert({p , p , ttime});
					}
				}
				else{
					ste.insert({p , p , ttime});
				}
				str[p-1] = '1';
			}
			else{
				// cerr << "ste : ";for(auto itr : ste)cerr << itr[0] << "," << itr[1] << "," << itr[2] << "   ";cerr << endl;
				auto it = --ste.upper_bound({p , inf , inf});
				auto pai = *it;
				// cerr << "pai : " << pai[0] << " " << pai[1] << " " << pai[2] << endl;
				update(pai[0] , pai[1] , ttime - pai[2]);
				ste.erase(it);
				if(pai[0] <= p-1)ste.insert({pai[0] , p-1 , ttime});
				if(p+1 <= pai[1])ste.insert({p+1 , pai[1] , ttime});
				str[p-1] = '0';
			}
		}	
		else{
			int a,b;
			cin >> a >> b;
			b--;
			// cerr << "QUERY : " << typ << " " << a << " " << b << endl;
			// cerr << "ste : ";for(auto itr : ste)cerr << itr[0] << "," << itr[1] << "," << itr[2] << "   ";cerr << endl;
			int cevap = query(a,b);
			auto it = ste.upper_bound({a , inf , inf});
			if(str[a-1] == '1' and it != ste.begin() and sz(ste)){
				// cerr << "flag0" << endl;
				auto pai = *--it;
				// cerr << "pai : " << pai[0] << " " << pai[1] << " " << pai[2] << endl;
				if(pai[0] <= a and pai[1] >= b){
					// cerr << "flag1" << endl;
					cevap += ttime - pai[2];
				}
			}
			cout << cevap << '\n';
		}
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

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