Submission #29855

# Submission time Handle Problem Language Result Execution time Memory
29855 2017-07-21T09:06:49 Z PrOAhMeT Cake (CEOI14_cake) C++14
0 / 100
563 ms 18856 KB
#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;
		it2=v.end();
		for(it=v.begin();it!=v.end();++it) {
			if(it->nd>=val.nd) {
				++it->nd;
				if(it->nd==11)
					it2=it;
			}
		}
		//cout<<"vinsert "<<val.st<<" "<<val.nd<<" "<<v.size()<<" "<<in<<endl;
		if(it2!=v.end()) v.erase(it2);
		//cout<<"ho "<<v.size()<<endl;
		if(!v.empty()) {
			for(it=v.begin();it!=v.end();++it) {
				if(it->st>val.st) {
					v.insert(it,val);
					break;
				}
			}
		}
		else v.insert(v.begin(),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) {
			lazy[1][x*2]=lazy[1][x];
			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

cake.cpp: In function 'void vinsert(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&, std::pair<int, int>)':
cake.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ot.size();++i)
               ^
cake.cpp:66: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:77: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:157: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:160:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&d[i]);
                    ^
cake.cpp:196:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
cake.cpp:198:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
                  ^
cake.cpp:200: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:231:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
                  ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 15700 KB Output is correct
2 Incorrect 0 ms 15700 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 323 ms 15972 KB Output isn't correct
2 Incorrect 179 ms 15972 KB Output isn't correct
3 Incorrect 446 ms 15972 KB Output isn't correct
4 Correct 309 ms 15972 KB Output is correct
5 Incorrect 473 ms 16168 KB Output isn't correct
6 Incorrect 273 ms 16168 KB Output isn't correct
7 Incorrect 563 ms 16168 KB Output isn't correct
8 Correct 309 ms 16168 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 17320 KB Output isn't correct
2 Incorrect 76 ms 17320 KB Output isn't correct
3 Incorrect 76 ms 17320 KB Output isn't correct
4 Incorrect 0 ms 15700 KB Output isn't correct
5 Incorrect 146 ms 18856 KB Output isn't correct
6 Incorrect 113 ms 18856 KB Output isn't correct
7 Incorrect 113 ms 18856 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 15840 KB Output isn't correct
2 Incorrect 36 ms 15840 KB Output isn't correct
3 Incorrect 89 ms 16552 KB Output isn't correct
4 Incorrect 73 ms 16552 KB Output isn't correct
5 Incorrect 96 ms 15700 KB Output isn't correct
6 Incorrect 149 ms 17320 KB Output isn't correct
7 Incorrect 129 ms 15972 KB Output isn't correct
8 Incorrect 246 ms 17320 KB Output isn't correct
9 Incorrect 536 ms 18856 KB Output isn't correct
10 Incorrect 343 ms 15700 KB Output isn't correct
11 Incorrect 343 ms 16168 KB Output isn't correct
12 Incorrect 529 ms 18856 KB Output isn't correct
13 Incorrect 416 ms 18856 KB Output isn't correct