Submission #1309099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309099		namhh	가로등 (APIO19_street_lamps)	C++20	100 / 100	1030 ms	67608 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 3e5+5;
int n,q,bits[2][N],val[N],ans[N];
string s;
vector<int>qr;
struct events{
	int id,l,r,t;
};
vector<events>loj;
bool cmp(events a, events b){
	return a.t < b.t;
}
bool cmp1(events a, events b){
	return a.r > b.r;
}
void update(int id, int u, int val){
	while(u <= n){
		bits[id][u] += val;
		u += u & (-u);
	}
}
int get(int id, int u){
	int sum = 0;
	while(u > 0){
		sum += bits[id][u];
		u -= u & (-u);
	}
	return sum;
}
set<int>st;
int cnp(int u){
	int l = 0;
	int r = loj.size()-1;
	int ans = loj.size();
	while(l <= r){
		int mid = (l+r)/2;
		if(loj[mid].t >= u){
			ans = mid;
			r = mid-1;
		}
		else l = mid+1;
	}
	return ans;
}
void dnc(int l, int r){
	if(l == r) return;
	int mid = (l+r)/2;
	dnc(l,mid);
	dnc(mid+1,r);
	int l1 = cnp(l);
	int r1 = cnp(mid+1)-1;
	if(l1 > r1) return;
	int l2 = r1+1;
	int r2 = cnp(r+1)-1;
	vector<events>diddy1,diddy2;
	for(int i = l1; i <= r1; i++){
	    if(loj[i].id != 0) diddy1.push_back(loj[i]);
	}
	for(int i = l2; i <= r2; i++){
	    if(loj[i].id == 0) diddy2.push_back(loj[i]);
	}
	sort(diddy1.begin(),diddy1.end(),cmp1);
	sort(diddy2.begin(),diddy2.end(),cmp1);
	int ptr = 0;
	for(auto[id,l3,r3,t]: diddy2){
		while(ptr < (int)diddy1.size() && diddy1[ptr].r >= r3){
			auto[id1,l4,r4,t1] = diddy1[ptr];
			update(0,l4,id1);
			update(1,l4,t1*id1);
			ptr++;
		}
		ans[t] += get(0,l3)*t-get(1,l3);
	}
	for(int i = ptr-1; i >= 0; i--){
		auto[id,l3,r3,t] = diddy1[i];
		update(0,l3,-id);
		update(1,l3,-t*id);
	}
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> q >> s;
	s = "#"+s;
	for(int i = 1; i <= n; i++){
		if(s[i] == '0') st.insert(i);
	}
	st.insert(0);
	st.insert(n+1);
	for(int i = 1; i <= q; i++){
		string type;
		cin >> type;
		if(type == "toggle"){
			int u;
			cin >> u;
			if(s[u] == '0'){
				auto y = st.upper_bound(u);
				auto x = st.lower_bound(u);
				--x;
				int l = *x;
				int r = *y;
				if(l < u-1){
					int dm = val[l];
					loj.push_back({1,l+1,u,dm});
					loj.push_back({-1,l+1,u,i});
				}
				if(u < r-1){
					int dm = val[u];
					loj.push_back({1,u+1,r,dm});
					loj.push_back({-1,u+1,r,i});
				}
				val[l] = i;
				st.erase(u);
				s[u] = '1';
			}
			else{
				auto y = st.upper_bound(u);
				auto x = st.lower_bound(u);
				--x;
				int l = *x;
				int r = *y;
				int dm = val[l];
				loj.push_back({1,l+1,r,dm});
				loj.push_back({-1,l+1,r,i});
				val[l] = val[u] = i;
				st.insert(u);
				s[u] = '0';
			}
		}
		else{
			int l,r;
			cin >> l >> r;
		    loj.push_back({0,l,r,i});
		    qr.push_back(i);
		}
	}
	vector<int>v;
	auto l = st.begin();
	while(l != st.end()){
		v.push_back(*l);
		++l;
	}
	for(int i = 1; i < (int)v.size(); i++){
		if(v[i-1] == v[i]-1) continue;
		int dm = val[v[i-1]];
		loj.push_back({1,v[i-1]+1,v[i],dm});
		loj.push_back({-1,v[i-1]+1,v[i],q+1});
	}
	sort(loj.begin(),loj.end(),cmp);
	dnc(0,qr.back());
	for(auto it: qr) cout << ans[it] << "\n";
}

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