Submission #202192

#	Time	Username	Problem	Language	Result	Execution time	Memory
202192		red1108	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	5088 ms	524288 KiB

street_lamps

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define eb emplace_back
#define em emplace
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;typedef long double ld;typedef unsigned long long ul;typedef unsigned int ui;typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 2e18;
const int inf = 2e9;
template<class T>
void pr(T t) {cerr << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cerr << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cerr << endl;}


int n,q,cur[300010];
tiii seg[1200000];
string in;
void gang(int x, int l, int r, int s, int e, int t){
	if(s>e||r<s||e<l) return ;
	if(s<=l&&r<=e){
		seg[x]=tiii(t,s,e);
		return ;
	}
	gang(x*2,l,(l+r)/2,s,e,t);gang(x*2+1,(l+r)/2+1,r,s,e,t);
}
tiii get(int x, int l, int r, int ind){
	if(ind<l||r<ind) return tiii(0,0,0);
	if(l==r) return seg[x];
	return max({seg[x],get(x*2,l,(l+r)/2,ind), get(x*2+1,(l+r)/2+1,r,ind)});
}
struct Node{
	int cnt=0, l=0, r=0;
	ll lsum=0, dsum=0;
	Node(){}
};
struct SEG{
	vector<Node> seg;
	SEG(){seg.eb(Node());seg.eb(Node());}
	void gang(int x, int l, int r, int ind, int t, int bac){
		if(l==r){
			if(bac==-1){
				seg[x].cnt+=1;
				seg[x].lsum+=t;
			}
			else{
				seg[x].cnt--;
				seg[x].dsum += (t - bac);
				seg[x].lsum -=bac;
			}
			return ;
		}
		int m = (l+r)/2;
		if(ind<=m){
			if(!seg[x].l){
				seg[x].l = seg.size();seg.eb(Node());
			}
			gang(seg[x].l,l,(l+r)/2,ind,t,bac);
		}
		else{
			if(!seg[x].r){
				seg[x].r = seg.size();seg.eb(Node());
			}
			gang(seg[x].r,(l+r)/2+1,r,ind,t,bac);
		}
		seg[x].cnt = seg[seg[x].l].cnt + seg[seg[x].r].cnt;
		seg[x].lsum = seg[seg[x].l].lsum + seg[seg[x].r].lsum;
		seg[x].dsum = seg[seg[x].l].dsum + seg[seg[x].r].dsum;
	}
	ll hap(int x, int l, int r, int ind, ll t){
		//prl("hap", x, l, r, ind, t);
		if(x==0||ind<l) return 0;
		if(r<=ind){
			return t * seg[x].cnt - seg[x].lsum + seg[x].dsum;
		}
		return hap(seg[x].l, l, (l+r)/2,ind, t) + hap(seg[x].r,(l+r)/2+1,r,ind,t);
	}
}fen[300010];
void add(int x, int y, int t){
	//prl("add", "x=",x,"y=",y,"time=",t);
	for(;x<=n;x+=x&-x){
		fen[x].gang(1,1,n,y,t,-1);
	}
}
void del(int x, int y, int t, int bac){
	for(;x<=n;x+=x&-x) fen[x].gang(1,1,n,y,t,bac);
}
ll hap(int x, int y, int t){
	//prl("hap", x, y, t);
	ll ret=0;
	for(;x>=1;x-=x&-x){
		//prl("x=", x);
		ret += fen[x].hap(1,1,n,y,t);
	}
	return ret;
}
int main(){
	fastio;
	cin>>n>>q;
	cin>>in;
	int bac = 1;
	n++;
	for(int i=0;i<n-1;i++){
		cur[i+1]=in[i]-'0';
		if(in[i]=='0') {
			gang(1,1,n,bac,i+1,0);
			add(bac,n-i,0);
			bac = i+2;
		}
	}
	gang(1,1,n,bac,n,0);
	add(bac,1,0);
	for(int i=1;i<=q;i++){
		string c;int a, b;
		cin>>c;
		if(c[0]=='q'){
			cin>>a>>b;
			cout<<hap(a,n-b+1,i)<<"\n";
		}
		else{
			cin>>a;
			int l,r,x,t;
			if(cur[a]){
				tie(t,l,r) = get(1,1,n,a);
				del(l,n-r+1,i,t);
				gang(1,1,n,l,a,i);
				gang(1,1,n,a+1,r,i);
				add(l,n-a+1,i);
				add(a+1,n-r+1,i);
			}
			else{
				tie(t,l,x) = get(1,1,n,a);
				del(l,n-x+1,i,t);
				tie(t,x,r) = get(1,1,n,a+1);
				del(x,n-r+1,i,t);
				gang(1,1,n,l,r,i);
				add(l,n-r+1,i);
			}
			cur[a]=!cur[a];
		}
	}
}

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