| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 233919 |
2020-05-22T11:40:47 Z |
Andrei_Cotor |
Cake (CEOI14_cake) |
C++11 |
|
374 ms |
7444 KB |
#include<iostream>
#include<algorithm>
using namespace std;
int Top10[15],A[250005],Coresp[250005]; //Coresp=cine imi scoate pozitia i (i<a). Pt update analizez ce se modifica la corespondenti
int Max[1000005],Lazy[1000005];
void build(int nod, int st, int dr)
{
Lazy[nod]=-1;
if(st==dr)
{
Max[nod]=Coresp[st];
return;
}
int mij=(st+dr)/2;
build(2*nod,st,mij);
build(2*nod+1,mij+1,dr);
Max[nod]=max(Max[2*nod],Max[2*nod+1]);
}
void propag(int nod, int st, int dr)
{
if(Lazy[nod]==-1)
return;
Max[nod]=Lazy[nod];
if(st!=dr)
{
Lazy[2*nod]=Lazy[nod];
Lazy[2*nod+1]=Lazy[nod];
}
Lazy[nod]=-1;
}
int src(int nod, int st, int dr, int val) //>val
{
if(st==dr)
{
if(Max[nod]<=val)
return 0;
return st;
}
int mij=(st+dr)/2;
propag(2*nod,st,mij);
propag(2*nod+1,mij+1,dr);
int rez;
if(Max[2*nod+1]>val)
rez=src(2*nod+1,mij+1,dr,val);
else
rez=src(2*nod,st,mij,val);
Max[nod]=max(Max[2*nod],Max[2*nod+1]);
return rez;
}
int query(int nod, int st, int dr, int poz)
{
if(st==dr)
return Max[nod];
int mij=(st+dr)/2;
propag(2*nod,st,mij);
propag(2*nod+1,mij+1,dr);
int rez;
if(poz<=mij)
rez=query(2*nod,st,mij,poz);
else
rez=query(2*nod+1,mij+1,dr,poz);
Max[nod]=max(Max[2*nod],Max[2*nod+1]);
return rez;
}
void update(int nod, int st, int dr, int l, int r, int val)
{
if(l<=st && dr<=r)
{
Lazy[nod]=val;
propag(nod,st,dr);
return;
}
int mij=(st+dr)/2;
propag(2*nod,st,mij);
propag(2*nod+1,mij+1,dr);
if(l<=mij)
update(2*nod,st,mij,l,r,val);
if(mij<r)
update(2*nod+1,mij+1,dr,l,r,val);
Max[nod]=max(Max[2*nod],Max[2*nod+1]);
}
void modif(int poz, int val) //pun in top10 pe poz val
{
int fin=10;
for(int i=poz; i<=10; i++)
{
if(Top10[i]==val)
{
fin=i;
break;
}
}
for(int i=fin-1; i>=poz; i--)
Top10[i+1]=Top10[i];
Top10[poz]=val;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,a;
cin>>n>>a;
for(int i=1; i<=n; i++)
{
cin>>A[i];
if(A[i]>n-10)
Top10[n-A[i]+1]=i;
}
int st=a-1;
int dr=a+1;
A[0]=A[n+1]=1000000000;
while(1)
{
if(st==0 && dr==n+1)
break;
if(A[st]<A[dr])
{
Coresp[st]=dr;
st--;
}
else
dr++;
}
build(1,1,a-1);
int nrq;
cin>>nrq;
for(int q=1; q<=nrq; q++)
{
char tip;
cin>>tip;
if(tip=='E')
{
int x,poz;
cin>>x>>poz;
if(x<a)
{
int coresp=query(1,1,a-1,x);
int scoate=n+1;
int lst=0; //cel mai din dreapta din st lui x care nu poate fi scos de scoate
for(int i=poz-1; i>=1; i--)
{
if(Top10[i]>=coresp)
{
if(scoate>Top10[i])
{
scoate=Top10[i];
lst=0;
}
}
else if(Top10[i]<x)
lst=max(lst,Top10[i]);
}
update(1,1,a-1,lst+1,x,scoate);
}
else if(x>a)
{
int coresp=src(1,1,a-1,x);
int scoate=0;
for(int i=poz-1; i>=1; i--)
{
if(Top10[i]<=coresp)
scoate=max(scoate,Top10[i]);
}
if(scoate+1<=coresp)
update(1,1,a-1,scoate+1,coresp,x);
}
modif(poz,x);
}
else
{
int x;
cin>>x;
if(x==a)
{
cout<<"0\n";
}
else if(x<a)
{
int coresp=query(1,1,a-1,x);
cout<<coresp-x-1<<"\n";
}
else
{
int coresp=src(1,1,a-1,x);
cout<<x-coresp-1<<"\n";
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
7 ms |
384 KB |
Output is correct |
| 5 |
Correct |
10 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
225 ms |
2284 KB |
Output is correct |
| 2 |
Correct |
177 ms |
2168 KB |
Output is correct |
| 3 |
Correct |
265 ms |
2296 KB |
Output is correct |
| 4 |
Correct |
156 ms |
2296 KB |
Output is correct |
| 5 |
Correct |
298 ms |
2424 KB |
Output is correct |
| 6 |
Correct |
230 ms |
2552 KB |
Output is correct |
| 7 |
Correct |
289 ms |
2680 KB |
Output is correct |
| 8 |
Correct |
189 ms |
2552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
3960 KB |
Output is correct |
| 2 |
Correct |
59 ms |
3832 KB |
Output is correct |
| 3 |
Correct |
54 ms |
3704 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
82 ms |
6200 KB |
Output is correct |
| 6 |
Correct |
77 ms |
6264 KB |
Output is correct |
| 7 |
Correct |
73 ms |
6008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
896 KB |
Output is correct |
| 2 |
Correct |
30 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
54 ms |
2304 KB |
Output is correct |
| 4 |
Correct |
55 ms |
2296 KB |
Output is correct |
| 5 |
Correct |
68 ms |
1784 KB |
Output is correct |
| 6 |
Correct |
94 ms |
3320 KB |
Output is correct |
| 7 |
Correct |
92 ms |
2680 KB |
Output is correct |
| 8 |
Correct |
132 ms |
3576 KB |
Output is correct |
| 9 |
Correct |
358 ms |
7444 KB |
Output is correct |
| 10 |
Correct |
218 ms |
3192 KB |
Output is correct |
| 11 |
Correct |
242 ms |
3852 KB |
Output is correct |
| 12 |
Correct |
374 ms |
6904 KB |
Output is correct |
| 13 |
Correct |
286 ms |
7160 KB |
Output is correct |
