#include <bits/stdc++.h>
#define DIM 250010
using namespace std;
struct segment_tree{
int maxi,poz;
} aint[DIM*4];
int v[DIM];
set <pair<int,int> > s;
vector <pair<int,int> > w;
int n,a,q,poz,sol_poz,val,sol,x,i;
char ch;
void build (int nod, int st, int dr){
if (st == dr){
aint[nod].maxi = v[st];
aint[nod].poz = st;
return;
}
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
if (aint[nod<<1].maxi > aint[(nod<<1)|1].maxi)
aint[nod] = aint[nod<<1];
else aint[nod] = aint[(nod<<1)|1];
}
void update (int nod, int st, int dr, int poz, int val){
if (st == dr){
aint[nod].maxi = val;
return;
}
int mid = (st+dr)>>1;
if (poz <= mid)
update (nod<<1,st,mid,poz,val);
else update ((nod<<1)|1,mid+1,dr,poz,val);
if (aint[nod<<1].maxi > aint[(nod<<1)|1].maxi)
aint[nod] = aint[nod<<1];
else aint[nod] = aint[(nod<<1)|1];
}
void query_maxi (int nod, int st, int dr, int x, int y){
if (x <= st && dr <= y){
sol = max (sol,aint[nod].maxi);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
query_maxi (nod<<1,st,mid,x,y);
if (y > mid)
query_maxi ((nod<<1)|1,mid+1,dr,x,y);
}
int get_val (int nod, int st, int dr, int poz){
if (st == dr)
return aint[nod].maxi;
int mid = (st+dr)>>1;
if (poz <= mid)
return get_val (nod<<1,st,mid,poz);
else return get_val ((nod<<1)|1,mid+1,dr,poz);
}
void query (int nod, int st, int dr, int x, int y, int val){
if (sol_poz)
return;
if (st == dr && aint[nod].maxi > val){
sol_poz = st;
return;
}
if (x <= st && dr <= y){
if (aint[nod].maxi > val){ /// inseamna ca trb sa i dau split
int mid = (st+dr)>>1;
if (aint[nod<<1].maxi <= val)
query ((nod<<1)|1,mid+1,dr,x,y,val);
else query ((nod<<1),st,mid,x,y,val);
}
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
query (nod<<1,st,mid,x,y,val);
if (y > mid)
query ((nod<<1)|1,mid+1,dr,x,y,val);
}
void query2 (int nod, int st, int dr, int x, int y, int val){
if (sol_poz)
return;
if (st == dr && aint[nod].maxi > val){
sol_poz = st;
return;
}
if (x <= st && dr <= y){
if (aint[nod].maxi > val){
int mid = (st+dr)>>1;
if (aint[(nod<<1)|1].maxi > val)
query2 ((nod<<1)|1,mid+1,dr,x,y,val);
else query2 (nod<<1,st,mid,x,y,val);
}
return;
}
int mid = (st+dr)>>1;
if (y > mid)
query2 ((nod<<1)|1,mid+1,dr,x,y,val);
if (x <= mid)
query2 (nod<<1,st,mid,x,y,val);
}
int main (){
//ifstream cin ("cake.in");
//ofstream cout ("cake.out");
cin>>n>>a;
for (i=1;i<=n;i++){
cin>>v[i];
s.insert(make_pair(v[i],i));
}
build (1,1,n);
cin>>q;
for (;q--;){
cin>>ch;
if (ch == 'E'){
cin>>poz>>x;
/// mai intai verific daca e cumva deja a x - a valoare
int pas = 0, ok = 0;
for (set<pair<int,int> > :: reverse_iterator it = s.rbegin();it != s.rend();it++){
pas++;
if (pas == x){
if (it->second == poz)
ok = 1;
break;
}
}
if (ok)
continue;
/// iau cele mai mari x-1 valori si pe poz o sa pun a x-1 a valoare
pas = 0;
int val = get_val (1,1,n,poz), aux = 0;
w.clear();
while (1){
set <pair<int,int> > :: reverse_iterator it = s.rbegin();
pas++;
if (pas == x){
aux = it->first;
update (1,1,n,poz,aux+1);
w.push_back(make_pair(aux+1,poz));
s.erase(make_pair(val,poz));
break;
}
update (1,1,n,it->second,it->first+1);
w.push_back(make_pair(it->first+1,it->second));
s.erase(make_pair(it->first,it->second));
}
for (auto it : w)
s.insert(make_pair(it.first,it.second));
// for (i=1;i<=n;i++)
// cout<<get_val(1,1,n,i)<<" ";
// cout<<"\n";
continue;
}
cin>>poz;
if (poz == a){
cout<<"0\n";
continue;
}
val = get_val (1,1,n,poz);
if (poz < a){ /// e in stanga
sol = 0;
query_maxi (1,1,n,poz,a-1);
sol_poz = 0;
query (1,1,n,a+1,n,sol);
if (!sol_poz) /// inseamna ca toate sunt mai mici
sol_poz = n+1;
cout<<sol_poz - poz - 1<<"\n";
} else {
sol = 0;
query_maxi (1,1,n,a+1,poz);
sol_poz = 0;
query2 (1,1,n,1,a-1,sol);
cout<<poz - sol_poz - 1<<"\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
6 ms |
512 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
23 ms |
512 KB |
Output is correct |
| 5 |
Correct |
40 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
980 ms |
2296 KB |
Output is correct |
| 2 |
Correct |
643 ms |
2296 KB |
Output is correct |
| 3 |
Correct |
736 ms |
2296 KB |
Output is correct |
| 4 |
Correct |
510 ms |
2296 KB |
Output is correct |
| 5 |
Correct |
1080 ms |
3192 KB |
Output is correct |
| 6 |
Correct |
956 ms |
3192 KB |
Output is correct |
| 7 |
Correct |
797 ms |
3192 KB |
Output is correct |
| 8 |
Correct |
569 ms |
3192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
410 ms |
9336 KB |
Output is correct |
| 2 |
Correct |
373 ms |
9208 KB |
Output is correct |
| 3 |
Correct |
348 ms |
9080 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
611 ms |
19128 KB |
Output is correct |
| 6 |
Correct |
612 ms |
19064 KB |
Output is correct |
| 7 |
Correct |
459 ms |
18808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
128 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
251 ms |
4984 KB |
Output is correct |
| 4 |
Correct |
305 ms |
5368 KB |
Output is correct |
| 5 |
Correct |
417 ms |
1912 KB |
Output is correct |
| 6 |
Correct |
471 ms |
6392 KB |
Output is correct |
| 7 |
Correct |
490 ms |
2728 KB |
Output is correct |
| 8 |
Correct |
468 ms |
8696 KB |
Output is correct |
| 9 |
Execution timed out |
2076 ms |
19792 KB |
Time limit exceeded |
| 10 |
Correct |
1406 ms |
2920 KB |
Output is correct |
| 11 |
Correct |
1619 ms |
4344 KB |
Output is correct |
| 12 |
Execution timed out |
2083 ms |
17400 KB |
Time limit exceeded |
| 13 |
Correct |
1830 ms |
20000 KB |
Output is correct |
