#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;
/// iau cele mai mari x-1 valori si pe poz o sa pun a x-1 a valoare
int pas = 0, val = 0;
w.clear();
while (1){
set <pair<int,int> > :: reverse_iterator it = s.rbegin();
pas++;
if (pas == x){
val = it->first;
update (1,1,n,it->second,it->first+1);
w.push_back(make_pair(it->first+1,it->second));
update (1,1,n,poz,val);
w.push_back(make_pair(val,poz));
s.erase(make_pair(it->first,it->second));
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));
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,val);
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,val);
cout<<poz - sol_poz - 1<<"\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1163 ms |
28952 KB |
Output isn't correct |
| 2 |
Incorrect |
858 ms |
29080 KB |
Output isn't correct |
| 3 |
Incorrect |
1002 ms |
29176 KB |
Output isn't correct |
| 4 |
Incorrect |
812 ms |
29176 KB |
Output isn't correct |
| 5 |
Incorrect |
1207 ms |
30456 KB |
Output isn't correct |
| 6 |
Incorrect |
1086 ms |
30712 KB |
Output isn't correct |
| 7 |
Incorrect |
1016 ms |
30480 KB |
Output isn't correct |
| 8 |
Incorrect |
840 ms |
30584 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
395 ms |
9464 KB |
Output isn't correct |
| 2 |
Incorrect |
348 ms |
9336 KB |
Output isn't correct |
| 3 |
Incorrect |
333 ms |
9420 KB |
Output isn't correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
606 ms |
20216 KB |
Output isn't correct |
| 6 |
Incorrect |
585 ms |
20268 KB |
Output isn't correct |
| 7 |
Incorrect |
445 ms |
20228 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
2168 KB |
Output isn't correct |
| 2 |
Incorrect |
123 ms |
2424 KB |
Output isn't correct |
| 3 |
Incorrect |
244 ms |
6836 KB |
Output isn't correct |
| 4 |
Incorrect |
277 ms |
6904 KB |
Output isn't correct |
| 5 |
Incorrect |
437 ms |
5368 KB |
Output isn't correct |
| 6 |
Incorrect |
440 ms |
10360 KB |
Output isn't correct |
| 7 |
Incorrect |
514 ms |
7928 KB |
Output isn't correct |
| 8 |
Incorrect |
534 ms |
19320 KB |
Output isn't correct |
| 9 |
Incorrect |
1977 ms |
36728 KB |
Output isn't correct |
| 10 |
Incorrect |
1463 ms |
17016 KB |
Output isn't correct |
| 11 |
Incorrect |
1659 ms |
19320 KB |
Output isn't correct |
| 12 |
Incorrect |
1959 ms |
34024 KB |
Output isn't correct |
| 13 |
Incorrect |
1838 ms |
36984 KB |
Output isn't correct |
