Submission #29892

#	Time	Username	Problem	Language	Result	Execution time	Memory
29892		PrOAhMeT	Cake (CEOI14_cake)	C++14	100 / 100	709 ms	18856 KiB

cake

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXN=250005;
int n,a,d[MAXN],x,y,ans[MAXN],q,z,t,lazy[2][MAXN*4],f[MAXN*4];
char c;
vector<pii>::iterator it,it2;

void vinsert(vector<pii> &v,vector<pii> &ot,pii val) {

	//cout<<"vinsert "<<val.st<<" "<<val.nd<<" "<<v.size()<<endl;
	int in=0,oldval=0;
	for(it=v.begin();it!=v.end();++it) {
		if(it->st==val.st) {
			in=1;
			oldval=it->nd;
		}
	}
	//cout<<"vinsert "<<val.st<<" "<<val.nd<<" "<<v.size()<<" "<<in<<endl;
	if(in==0) {
		//cout<<"vinsert "<<val.st<<" "<<val.nd<<" "<<v.size()<<" "<<in<<endl;
		for(it=v.begin();it!=v.end();++it) {
			if(it->nd>=val.nd) {
				++it->nd;
			}
		}
		//cout<<"vinsert "<<val.st<<" "<<val.nd<<" "<<v.size()<<" "<<in<<endl;
		for(int i=0;i<v.size();++i)
			if(v[i].nd==11) {
				v.erase(v.begin()+i);
				break;
			}
		//cout<<"ho "<<v.size()<<endl;
			int ok=0;
			//cout<<"adding "<<val.st<<" "<<val.nd<<endl;
		if(!v.empty()) {
			for(it=v.begin();it!=v.end();++it) {
				if(it->st>val.st) {
					v.insert(it,val);
					ok=1;
					break;
				}
			}
		}
		if(v.empty()) v.insert(v.begin(),val);
		else if(!ok) v.pb(val);
	}
	else {
		for(it=v.begin();it!=v.end();++it) {
			if(it->st==val.st)
				it->nd=val.nd;
			else if(it->nd>=val.nd&&it->nd<oldval) {
				++it->nd;
			}
		}
	}

	for(int i=0;i<ot.size();++i)
		if(in==0&&ot[i].nd>=val.nd)
			++ot[i].nd;
		else if(in==1&&ot[i].nd>=val.nd&&ot[i].nd<oldval)
			++ot[i].nd;
	if(in==0) {
		for(int i=0;i<ot.size();++i)
			if(ot[i].nd==11) {
				ot.erase(ot.begin()+i);
				break;
			}
	}

}

int find(vector<pii> &v,int val,int no) {

	for(int i=0;i<v.size();++i) {
		if(v[i].st!=-a&&v[i].nd<val) {
			if(no==0) return -v[i].st;
			else return v[i].st; 
		}
	}
	return no;

}

void push(int x,int l,int r) {

	if(lazy[0][x]!=-1) {
		f[x]=lazy[0][x];
		if(l!=r) {
			lazy[0][x*2]=lazy[0][x];
			lazy[0][x*2+1]=lazy[0][x];
			lazy[1][x*2]=-1;
			lazy[1][x*2+1]=-1;
		}
		lazy[0][x]=-1;
	}
	if(lazy[1][x]!=-1) {
		f[x]=min(f[x],lazy[1][x]);
		if(l!=r) {
			if(lazy[1][x*2]==-1)
				lazy[1][x*2]=lazy[1][x];
			else lazy[1][x*2]=min(lazy[1][x*2],lazy[1][x]);
			if(lazy[1][x*2+1]==-1) 
				lazy[1][x*2+1]=lazy[1][x];
			else lazy[1][x*2+1]=min(lazy[1][x*2+1],lazy[1][x]);
		}
		lazy[1][x]=-1;		
	}

}

void build(int x,int l,int r) {

	lazy[0][x]=lazy[1][x]=-1;
	if(l==r) {
		f[x]=ans[l];
		return;
	}
	int md=(l+r)/2;
	build(x*2,l,md);
	build(x*2+1,md+1,r);

}

void upd(int x,int l,int r,int ll,int rr,int val,int upt) {

	if(lazy[0][x]!=-1||lazy[1][x]!=-1)
		push(x,l,r);
	if(l>rr||r<ll)
		return;
	if(l>=ll&&r<=rr) {
		lazy[upt][x]=val;
		push(x,l,r);
		return;
	}
	int md=(l+r)/2;
	upd(x*2,l,md,ll,rr,val,upt);
	upd(x*2+1,md+1,r,ll,rr,val,upt);

}

int que(int x,int l,int r,int ll) {

	if(lazy[0][x]!=-1||lazy[1][x]!=-1)
		push(x,l,r);
	if(l==ll&&r==ll)
		return f[x];
	int md=(l+r)/2;
	if(ll<=md)
		return que(x*2,l,md,ll);
	else return que(x*2+1,md+1,r,ll);

}

int main() {

	vector<pii> l,r;
	scanf("%d %d",&n,&a);
	priority_queue<pii> pq;
	for(int i=1;i<=n;++i) {
		scanf("%d",&d[i]);
		pq.push(mp(d[i],i));
	}
	for(int i=0;i<10&&!pq.empty();++i) {
		x=pq.top().st,y=pq.top().nd;
		pq.pop();
		if(y>a)
			r.pb(mp(y,i+1));
		else if(y<=a)
			l.pb(mp(-y,i+1));
	}
	sort(r.begin(),r.end());
	sort(l.begin(),l.end());
	int ll=a-1,rr=a+1;
	while(ll>=1||rr<=n) {
		if(ll>=1&&rr<=n) {
			if(d[ll]>d[rr]) {
				ans[rr]=a-ll;
				++rr;
			}
			else {
				ans[ll]=rr-a;
				--ll;
			}
		}
		else if(ll>=1) {
			ans[ll]=rr-a;
			--ll;
		}
		else {
			ans[rr]=a-ll;
			++rr;
		}
	}
	ans[a]=0;
	build(1,1,n);
	scanf("%d",&q);
	for(int i=0;i<q;++i) {
		scanf(" %c",&c);
		if(c=='E') {
			scanf("%d %d",&x,&y);
			if(x<=a) 
				vinsert(l,r,mp(-x,y));
			else vinsert(r,l,mp(x,y));
			if(x<a) {
				/*cout<<"left "<<l.size()<<endl;
				for(int i=0;i<l.size();++i)
					cout<<-l[i].st<<" "<<l[i].nd<<endl;
				cout<<endl;
				cout<<"right "<<r.size()<<endl;
				for(int i=0;i<r.size();++i)
					cout<<r[i].st<<" "<<r[i].nd<<endl;
				cout<<endl;*/
				t=find(l,y,0);
				if(t<x) {
					z=find(r,y,n+1);
					upd(1,1,n,t+1,x,z-a,0);
					upd(1,1,n,a+1,z-1,a-x,1);
				}
				//cout<<"find "<<t<<" "<<z<<endl;
			}
			else if(x>a) {
				t=find(r,y,n+1);
				if(t>x) {
					z=find(l,y,0);
					upd(1,1,n,x,t-1,a-z,0);
					upd(1,1,n,z+1,a-1,x-a,1);
				}
			}
		}
		else {
			scanf("%d",&x);
			if(x!=a) printf("%d\n",que(1,1,n,x)+(x<=a?a-x-1:x-a-1));
			else puts("0");
		}
	}

}

Compilation message (stderr)

cake.cpp: In function 'void vinsert(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&, std::pair<int, int>)':
cake.cpp:35:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();++i)
                ^
cake.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ot.size();++i)
               ^
cake.cpp:71:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<ot.size();++i)
                ^
cake.cpp: In function 'int find(std::vector<std::pair<int, int> >&, int, int)':
cake.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();++i) {
               ^
cake.cpp: In function 'int main()':
cake.cpp:165:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&a);
                      ^
cake.cpp:168:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&d[i]);
                    ^
cake.cpp:204:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
cake.cpp:206:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
                  ^
cake.cpp:208:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&x,&y);
                        ^
cake.cpp:239:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
                  ^

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50