#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, aux = 0;
int val = get_val (1,1,n,poz);
w.clear();
while (1){
set <pair<int,int> > :: reverse_iterator it = s.rbegin();
pas++;
if (pas == x){
aux = 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,aux+1);
w.push_back(make_pair(aux+1,poz));
s.erase(make_pair(it->first,it->second));
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));
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 |
1154 ms |
1272 KB |
Output isn't correct |
| 2 |
Incorrect |
772 ms |
1152 KB |
Output isn't correct |
| 3 |
Incorrect |
889 ms |
1280 KB |
Output isn't correct |
| 4 |
Incorrect |
658 ms |
1152 KB |
Output isn't correct |
| 5 |
Incorrect |
1239 ms |
2296 KB |
Output isn't correct |
| 6 |
Incorrect |
1094 ms |
2176 KB |
Output isn't correct |
| 7 |
Incorrect |
967 ms |
2176 KB |
Output isn't correct |
| 8 |
Incorrect |
753 ms |
2168 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
401 ms |
8312 KB |
Output isn't correct |
| 2 |
Incorrect |
351 ms |
8056 KB |
Output isn't correct |
| 3 |
Incorrect |
340 ms |
8184 KB |
Output isn't correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
607 ms |
17888 KB |
Output isn't correct |
| 6 |
Incorrect |
591 ms |
18040 KB |
Output isn't correct |
| 7 |
Incorrect |
444 ms |
17844 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
162 ms |
760 KB |
Output isn't correct |
| 2 |
Incorrect |
130 ms |
1016 KB |
Output isn't correct |
| 3 |
Incorrect |
266 ms |
4124 KB |
Output isn't correct |
| 4 |
Incorrect |
293 ms |
4216 KB |
Output isn't correct |
| 5 |
Incorrect |
432 ms |
888 KB |
Output isn't correct |
| 6 |
Incorrect |
504 ms |
5244 KB |
Output isn't correct |
| 7 |
Incorrect |
525 ms |
1836 KB |
Output isn't correct |
| 8 |
Incorrect |
563 ms |
7544 KB |
Output isn't correct |
| 9 |
Execution timed out |
2087 ms |
18908 KB |
Time limit exceeded |
| 10 |
Incorrect |
1425 ms |
1568 KB |
Output isn't correct |
| 11 |
Incorrect |
1698 ms |
3620 KB |
Output isn't correct |
| 12 |
Execution timed out |
2082 ms |
16324 KB |
Time limit exceeded |
| 13 |
Incorrect |
1953 ms |
19064 KB |
Output isn't correct |
