Submission #518319

#	Time	Username	Problem	Language	Result	Execution time	Memory
518319		CSQ31	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1314 ms	37088 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 reset(int i){
		for(;i<=n;i+=i&(-i))bit[i]=0;
	}
	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(){}
	fenwick(int _n){
		n = _n;
		bit.assign(n+1,0);
	}
	
}sum,num,f;
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;
	}
	
};vector<line>lines;

struct qq{
	int l,r,t;
	qq(){};
	qq(int _l,int _r,int _t):l(_l),r(_r),t(_t){}
};vector<qq>que;

const int MAXN = 3e5+5;
line st[MAXN];
int n,q,cnt = 0,ans[MAXN];
set<int>pos; //position of line heads
vector<array<int,2>>a;

/*
 * 	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;
				} 	
			}
		}
		
	}
* */
void solve(int s,int t){
	if(s == t)return;
	int mid = (s+t)/2;
	solve(s,mid);
	solve(mid+1,t);
	vector<array<int,2>>add,ask;
	for(int i=s;i<=mid;i++){
		int x = a[i][1];
		if(x >= 0){
			add.push_back({lines[x].tl,x});
			add.push_back({lines[x].tr+1,x});
		}
	}
	for(int i=mid+1;i<=t;i++){
		int x = a[i][1];
		if(x < 0){
			x++;
			x*=-1;
			ask.push_back({que[x].t,x});
		}
	}
	sort(add.begin(),add.end());
	sort(ask.begin(),ask.end());
	/*
	if(t==3){
		cout<<"ranges"<<'\n';
		cout<<s<<" "<<mid<<" "<<t<<'\n';
		cout<<"add"<<'\n';
		for(auto x:add)cout<<x[0]<<" "<<x[1]<<'\n';
		cout<<"ask"<<'\n';
		for(auto x:ask)cout<<x[0]<<" "<<x[1]<<'\n';
	}*/
	int ptr = -1;
	for(auto x:ask){
		while(ptr+1 < sz(add) && add[ptr+1][0] <= x[0]){
			ptr++;
			int id = add[ptr][1];
			if(lines[id].tl == add[ptr][0]){ //add a line into the tl<=t<=tr case
				sum.upd(lines[id].qr,lines[id].tl);
				num.upd(lines[id].qr,1);
			}else{ //delete a line from tl<=t<r case then add into tl<=tr<t case
				sum.upd(lines[id].qr,-lines[id].tl);
				num.upd(lines[id].qr,-1);
				f.upd(lines[id].qr,lines[id].tr - lines[id].tl + 1);
			}
		}
		int y = x[1];
		ans[y]+= f.query(n) - f.query(que[y].r-1);
		/*
		if(t==3){
			cout<<f.query(n)<<" "<<f.query(que[y].r-1)<<'\n';
			cout<<que[y].r-1<<" "<<num.query(n)<<" "<<num.query(n) - num.query(que[y].r-1)<<'\n';
		}*/
		ans[y] += (num.query(n) - num.query(que[y].r-1)) * (que[y].t) - (sum.query(n) - sum.query(que[y].r-1));
	}
	for(int i=0;i<=ptr;i++){
		int id = add[i][1];
		sum.reset(lines[id].qr);
		num.reset(lines[id].qr);
		f.reset(lines[id].qr);
	}
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	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.push_back(qq(l,r-1,i)); cnt++;
			a.push_back({l,-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]);
		}
	}
	for(int i=0;i<sz(lines);i++){
		a.push_back({lines[i].ql,i});
	}
	//for(auto x:lines)cout<<x.tl<<" "<<x.tr<<" "<<x.ql<<" "<<x.qr<<'\n';
	sort(a.begin(),a.end(),[&](array<int,2> i,array<int,2> j){
		if(i[0] == j[0])return j[1] < i[1];
	    return i[0] < j[0];
		}
	);
	sum = fenwick(n);
	num = fenwick(n);
	f = fenwick(n);
	/*
	cout<<"LINES"<<'\n';
	for(auto x:lines)cout<<x.tl<<" "<<x.tr<<" "<<x.ql<<" "<<x.qr<<'\n';
	for(auto x:a)cout<<x[0]<<" "<<x[1]<<'\n';
	* */
	solve(0,sz(a)-1);
	for(int i=0;i<cnt;i++)cout<<ans[i]<<'\n';
}
/*
5 8
01010
toggle 1
toggle 1
toggle 1
toggle 1
query 1 3
toggle 1
query 1 2
query 1 3
*/

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