Submission #535283

#	Time	Username	Problem	Language	Result	Execution time	Memory
535283		new_acc	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	6 ms	12188 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e5+10;
const int SS=1<<19;
int lazy[SS*2+10],seg[SS*2+10],seg2[SS*2+10],naj[N];
int sp[N],ans[N];
vector<pair<int,int> >zap[N];
void push(int v){
	seg[v*2]+=lazy[v],seg[v*2+1]+=lazy[v];
	lazy[v*2]+=lazy[v],lazy[v*2+1]+=lazy[v];
	lazy[v]=0;
}
void upd(int pocz,int kon,int x,int p=0,int k=SS-1,int v=1){
	if(p>kon or k<pocz) return;
	if(p>=pocz and k<=kon){
		seg[v]+=x,lazy[v]+=x;
		return;
	}
	push(v);
	upd(pocz,kon,x,p,(p+k)>>1,(v<<1)),upd(pocz,kon,x,((p+k)>>1)+1,k,(v<<1)+1);
	seg[v]=min(seg[v<<1],seg[(v<<1)+1]);
}
int Query(int pocz,int kon,int p=0,int k=SS-1,int v=1){
	if(p>kon or k<pocz) return INT_MAX;
	if(p>=pocz and k<=kon) return seg[v];
	push(v);
	return min(Query(pocz,kon,p,(p+k)>>1,v<<1),Query(pocz,kon,((p+k)>>1)+1,k,(v<<1)+1));
}
void upd2(int a,int ind){
	for(ind+=SS;ind>0;ind>>=1) seg2[ind]+=a;
}
int Query2(int a,int b){
	int res=0;
	for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
		if(!(a&1)) res+=seg2[a+1];
		if(b&1) res+=seg2[b-1];
	}
	return res;
}
void single(int x){
	for(auto u:zap[x]){
		int pom=Query(x,u.fi)-Query(u.fi+1,u.fi+1);
		ans[u.se]=Query2(x,u.fi)+(pom>0?0:abs(pom));
	}
	if(sp[x]>sp[x-1]){
		if(naj[x-1]!=-1) upd2(-1,naj[x-1]),upd(1,naj[x-1],-1);
		if(naj[x]!=-1) upd2(1,naj[x]),upd(1,naj[x],1);
	}
}
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		char a;
		cin>>a;
		if(a=='C') sp[i]=sp[i-1]+1;
		else sp[i]=sp[i-1]-1;
	}
	deque<pair<int,int> >deq;
	for(int i=n;i>=0;i--){
		while(deq.size() and deq.back().fi>=sp[i]) deq.pop_back();
		if(deq.size()) naj[i]=deq.back().se;
		else naj[i]=-1;
		deq.push_back({sp[i],i});
	}
	for(int i=1;i<=n;i++){
		if(sp[i]>sp[i-1]) upd(1,i,1);
		else upd(1,i,-1);
	}
	int curr=naj[0];
	while(curr!=-1){
		upd(1,curr,1);
		upd2(1,curr);
		curr=naj[curr];
	}
	int q;
	cin>>q;
	for(int i=1;i<=q;i++){
		int a,b;	
		cin>>a>>b;
		zap[a].push_back({b,i});
	}
	for(int i=1;i<=n;i++) single(i);
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}
int main(){
	solve();
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55