답안 #29849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29849 2017-07-21T08:41:32 Z PrOAhMeT 케이크 (CEOI14_cake) C++14
0 / 100
1129 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,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;
			}
		}
	}

}

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,mp(-x,y));
			else vinsert(r,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 'int find(std::vector<std::pair<int, int> >&, int, int)':
cake.cpp:64: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:144: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:147:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&d[i]);
                    ^
cake.cpp:183:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
cake.cpp:185:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
                  ^
cake.cpp:187: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:218:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
                  ^
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 15700 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 296 ms 15972 KB Output isn't correct
2 Incorrect 189 ms 15972 KB Output isn't correct
3 Incorrect 456 ms 15972 KB Output isn't correct
4 Correct 306 ms 15972 KB Output is correct
5 Incorrect 706 ms 16168 KB Output isn't correct
6 Incorrect 243 ms 16168 KB Output isn't correct
7 Incorrect 1129 ms 16168 KB Output isn't correct
8 Correct 326 ms 16168 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 106 ms 17320 KB Output isn't correct
2 Incorrect 86 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 129 ms 18856 KB Output isn't correct
6 Incorrect 113 ms 18856 KB Output isn't correct
7 Incorrect 89 ms 18856 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 15840 KB Output isn't correct
2 Incorrect 46 ms 15840 KB Output isn't correct
3 Incorrect 86 ms 16552 KB Output isn't correct
4 Incorrect 93 ms 16552 KB Output isn't correct
5 Incorrect 79 ms 15700 KB Output isn't correct
6 Incorrect 139 ms 17320 KB Output isn't correct
7 Incorrect 126 ms 15972 KB Output isn't correct
8 Incorrect 306 ms 17320 KB Output isn't correct
9 Incorrect 486 ms 18856 KB Output isn't correct
10 Incorrect 289 ms 15700 KB Output isn't correct
11 Incorrect 326 ms 16168 KB Output isn't correct
12 Incorrect 526 ms 18856 KB Output isn't correct
13 Incorrect 506 ms 18856 KB Output isn't correct