제출 #517021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
517021		CSQ31	가로등 (APIO19_street_lamps)	C++17	20 / 100	5086 ms	34912 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define sz(a) (int)(a.size())
struct fenwick{
	vector<ll>bit;
	int n;
	void upd(int i,int x){
		for(;i<=n;i+=i&(-i))bit[i]+=x;
	}
	ll query(int i){
		ll res = 0;
		for(;i>0;i-=i&(-i))res+=bit[i];
		return res;
	}
	fenwick(int _n){
		n = _n;
		bit.assign(n+1,0);
	}
	
};
struct line{
	int tl,tr,ql,qr;
	line(){}
	line(int _tl,int _tr,int _ql,int _qr){
		tl = _tl;
		tr = _tr;
		ql = _ql;
		qr = _qr;
	}
	
};
struct qq{
	int l,r,i;
	qq(){};
	qq(int _l,int _r,int _i):l(_l),r(_r),i(_i){}
};
const int MAXN = 3e5+5;
line st[MAXN];
int ans[MAXN];
set<int>pos; //position of line heads

vector<int>add[MAXN];
vector<qq>que[MAXN];
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,q,cnt = 0;
	vector<line>lines;
	string s = "0",ss;
	
	cin>>n>>q>>ss;
	s+=ss;
	for(int i=1;i<=n;i++){
		if(s[i] == '0')continue;
		int j = i;
		while(j+1<=n && s[j+1] == '1')j++;
		st[i] = line(0,0,i,j);
		pos.insert(i);
		i = j;
	}
	for(int i=1;i<=q;i++){
		string u;
		cin>>u;
		if(u == "toggle"){
			int x;
			cin>>x;
			if(s[x] == '0'){
				s[x] = '1';
				pos.insert(x);
				st[x] = line(i,i,x,x);
				auto it = pos.upper_bound(x);
				int v = 0;
				if(it != pos.end() && st[*it].ql == x+1){ //new line segment on right side with x as head
					v = *it;
					st[v].tr = i-1; 
					lines.push_back(st[v]);
					//cout<<st[v].tl<<" "<<st[v].tr<<" "<<st[v].ql<<" "<<st[v].qr<<'\n';
					st[x] = line(i,i,x,st[v].qr);
					pos.erase(it);
				}
				it = pos.lower_bound(x);
				if(it == pos.begin())continue;
				it--;
				if(st[*it].qr == x-1){ //new line segment on left side
					v = *it;
					st[v].tr = i-1;
					lines.push_back(st[v]);
					
					int L = st[v].ql;
					st[L] = line(i,i,L,st[x].qr);
					pos.erase(x);
				}
			}else{
				s[x] = '0';
				auto it = pos.upper_bound(x);
				it--;
				int v = *it;

				if(st[v].qr >=x){ //destroy a segment
					st[v].tr = i-1;
					lines.push_back(st[v]);
					
					if(st[v].qr > x){ //line seg on right
						pos.insert(x+1);
						st[x+1] = line(i,i,x+1,st[v].qr);
					}
					if(v != x)st[v] = line(i,i,st[v].ql,x-1); //line seg on left
				}
				pos.erase(x);
			}
		}else{
			int l,r;
			cin>>l>>r;
			que[i].push_back(qq(l,r-1,cnt++));
		}
		
	}
	for(int i=1;i<=n;i++){
		if(s[i] == '1' && (!i || s[i-1] == '0')){
			st[i].tr = q;
		   	lines.push_back(st[i]);
		}
	}
	
	//this part optimize to logn
	for(int i=1;i<=q;i++){
		for(auto q:que[i]){
			for(auto y:lines){
				if(y.tl <= i && y.ql <= q.l && q.r <= y.qr){
					ans[q.i]+=min(y.tr+1,i) - y.tl;
				} 	
			}
		}
		
	}
	for(int i=0;i<cnt;i++)cout<<ans[i]<<'\n';
}

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