답안 #29869

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29869 2017-07-21T09:43:50 Z PrOAhMeT 케이크 (CEOI14_cake) C++14
0 / 100
593 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) {
			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: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:160: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:163:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&d[i]);
                    ^
cake.cpp:199:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
cake.cpp:201:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
                  ^
cake.cpp:203: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:234: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 Incorrect 0 ms 15700 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 283 ms 15972 KB Output isn't correct
2 Correct 293 ms 15972 KB Output is correct
3 Incorrect 413 ms 15972 KB Output isn't correct
4 Correct 326 ms 15972 KB Output is correct
5 Incorrect 519 ms 16168 KB Output isn't correct
6 Incorrect 369 ms 16168 KB Output isn't correct
7 Incorrect 569 ms 16168 KB Output isn't correct
8 Correct 386 ms 16168 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 106 ms 17320 KB Output isn't correct
2 Incorrect 76 ms 17320 KB Output isn't correct
3 Incorrect 69 ms 17320 KB Output isn't correct
4 Correct 0 ms 15700 KB Output is correct
5 Incorrect 129 ms 18856 KB Output isn't correct
6 Correct 123 ms 18856 KB Output is correct
7 Correct 93 ms 18856 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 15840 KB Output isn't correct
2 Incorrect 43 ms 15840 KB Output isn't correct
3 Incorrect 106 ms 16552 KB Output isn't correct
4 Incorrect 89 ms 16552 KB Output isn't correct
5 Incorrect 113 ms 15700 KB Output isn't correct
6 Incorrect 146 ms 17320 KB Output isn't correct
7 Incorrect 123 ms 15972 KB Output isn't correct
8 Incorrect 239 ms 17320 KB Output isn't correct
9 Incorrect 563 ms 18856 KB Output isn't correct
10 Incorrect 329 ms 15700 KB Output isn't correct
11 Incorrect 286 ms 16168 KB Output isn't correct
12 Incorrect 593 ms 18856 KB Output isn't correct
13 Incorrect 463 ms 18856 KB Output isn't correct