#include <bits/stdc++.h>
#define DIM 250010
#define DIMBUFF 5000000
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,pos;
char ch;
char buff[DIMBUFF];
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 get_nr (){
while (!(buff[pos] >= '0' && buff[pos] <= '9'))
pos++;
int nr = 0;
while (buff[pos] >= '0' && buff[pos] <= '9'){
nr = nr*10 + buff[pos] - '0';
pos++;
}
return nr;
}
char get_char (){
while (buff[pos] != 'E' && buff[pos] != 'F')
pos++;
char ch = buff[pos];
pos++;
return ch;
}
int main (){
//FILE *fin = fopen ("cake.in","r");
//FILE *fout = fopen ("cake.out","w");
FILE *fin = stdin;
FILE *fout = stdout;
fread (buff,1,DIMBUFF,fin);
n = get_nr(), a = get_nr();
//cin>>n>>a;
for (i=1;i<=n;i++){
//cin>>v[i];
v[i] = get_nr();
s.insert(make_pair(v[i],i));
}
build (1,1,n);
//cin>>q;
q = get_nr();
for (;q--;){
//cin>>ch;
ch = get_char();
if (ch == 'E'){
// cin>>poz>>x;
poz = get_nr(), x = get_nr();
/// 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;
poz = get_nr();
if (poz == a){
fprintf(fout,"0\n");
//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";
fprintf(fout,"%d\n",sol_poz - poz - 1);
} 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";
fprintf(fout,"%d\n",poz - sol_poz - 1);
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:147:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread (buff,1,DIMBUFF,fin);
~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
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 |
10 ms |
512 KB |
Output is correct |
| 5 |
Correct |
21 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
624 ms |
5624 KB |
Output is correct |
| 2 |
Correct |
266 ms |
5504 KB |
Output is correct |
| 3 |
Correct |
355 ms |
5504 KB |
Output is correct |
| 4 |
Correct |
134 ms |
5504 KB |
Output is correct |
| 5 |
Correct |
685 ms |
6856 KB |
Output is correct |
| 6 |
Runtime error |
537 ms |
14736 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Correct |
408 ms |
7032 KB |
Output is correct |
| 8 |
Runtime error |
201 ms |
14072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
9468 KB |
Output is correct |
| 2 |
Correct |
69 ms |
9336 KB |
Output is correct |
| 3 |
Correct |
58 ms |
9336 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
224 ms |
20284 KB |
Output is correct |
| 6 |
Correct |
217 ms |
20216 KB |
Output is correct |
| 7 |
Correct |
94 ms |
20088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
44 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
104 ms |
4984 KB |
Output is correct |
| 4 |
Correct |
142 ms |
4984 KB |
Output is correct |
| 5 |
Correct |
178 ms |
1952 KB |
Output is correct |
| 6 |
Correct |
181 ms |
6776 KB |
Output is correct |
| 7 |
Correct |
162 ms |
3192 KB |
Output is correct |
| 8 |
Correct |
251 ms |
10048 KB |
Output is correct |
| 9 |
Runtime error |
1168 ms |
50016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Correct |
582 ms |
5240 KB |
Output is correct |
| 11 |
Correct |
785 ms |
7576 KB |
Output is correct |
| 12 |
Runtime error |
1153 ms |
44412 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
812 ms |
50024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
