| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 29892 |
2017-07-21T10:11:08 Z |
PrOAhMeT |
Cake (CEOI14_cake) |
C++14 |
|
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);
^
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
