답안 #29892

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29892 2017-07-21T10:11:08 Z PrOAhMeT 케이크 (CEOI14_cake) C++14
100 / 100
709 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;
		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

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);
                  ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 15700 KB Output is correct
2 Correct 0 ms 15700 KB Output is correct
3 Correct 0 ms 15700 KB Output is correct
4 Correct 3 ms 15700 KB Output is correct
5 Correct 9 ms 15972 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 376 ms 15972 KB Output is correct
2 Correct 293 ms 15972 KB Output is correct
3 Correct 496 ms 15972 KB Output is correct
4 Correct 366 ms 15972 KB Output is correct
5 Correct 599 ms 16168 KB Output is correct
6 Correct 399 ms 16168 KB Output is correct
7 Correct 536 ms 16168 KB Output is correct
8 Correct 343 ms 16168 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 17320 KB Output is correct
2 Correct 99 ms 17320 KB Output is correct
3 Correct 73 ms 17320 KB Output is correct
4 Correct 0 ms 15700 KB Output is correct
5 Correct 139 ms 18856 KB Output is correct
6 Correct 129 ms 18856 KB Output is correct
7 Correct 83 ms 18856 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 15840 KB Output is correct
2 Correct 46 ms 15840 KB Output is correct
3 Correct 103 ms 16552 KB Output is correct
4 Correct 83 ms 16552 KB Output is correct
5 Correct 143 ms 15700 KB Output is correct
6 Correct 149 ms 17320 KB Output is correct
7 Correct 146 ms 15972 KB Output is correct
8 Correct 293 ms 17320 KB Output is correct
9 Correct 579 ms 18856 KB Output is correct
10 Correct 353 ms 15700 KB Output is correct
11 Correct 399 ms 16168 KB Output is correct
12 Correct 709 ms 18856 KB Output is correct
13 Correct 513 ms 18856 KB Output is correct