This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
vector<int> lst, rst;
int value[250100];
int ord[750100];
int pre[750100];
int n, q, a, maxv;
int arr[250100];
int getbef(int idx) {
if (pre[idx]==-1||~ord[pre[idx]]) return pre[idx];
return pre[idx] = (getbef(pre[idx]));
}
vector<int> comp;
void com(int arr[], int val[]) {
int i;
for (i=0;i<n;i++) comp.push_back(arr[i]);
sort(comp.begin(),comp.end());
for (i=0;i<n;i++) val[i] = lower_bound(comp.begin(),comp.end(),arr[i])-comp.begin();
}
void push(vector<int> &st, int val) {
if (st.empty()||value[st.back()]<value[val]) st.push_back(val);
}
void deb() {
int i;
for (i=0;i<lst.size();i++) {
printf("%d : %d, ",lst[i],value[lst[i]]);
}
printf("\n");
for (i=0;i<rst.size();i++) {
printf("%d : %d, ",rst[i],value[rst[i]]);
}
printf("\n\n");
/*
for (i=0;i<n;i++) printf("%d ",value[i]);
printf("\n");
for (i=0;i<=maxv;i++) printf("%d ",ord[i]);
printf("\n");
*/
}
stack<int> tt;
void stupd(vector<int> &st, int idx, int sg) {
while(!st.empty()&&st.back()*sg>=idx*sg) {
tt.push(st.back());
st.pop_back();
}
if (tt.empty()||tt.top()!=idx) tt.push(idx);
while(!tt.empty()) {
push(st,tt.top());
tt.pop();
}
}
vector<int> can;
void upd(int idx, int e) {
can.clear();
int i, p = maxv;
for (i=0;i<e-1;i++) {
can.push_back(p);
p = getbef(p);
}
can.push_back(value[idx]);
int q = value[idx];
maxv++;
for (i=0;i<can.size();i++) {
value[ord[can[i]]] = ((i)?can[i-1]:maxv);
ord[((i)?can[i-1]:maxv)] = ord[can[i]];
}
ord[q] = -1;
if (idx<a) stupd(lst,idx,-1);
else if (idx>a) stupd(rst,idx,1);
}
int ibs(vector<int> &st, int idx, int sg) {
int s = 0, e = (int)st.size()-1;
while(s<=e) {
int m = (s+e)>>1;
if (sg*st[m]<=sg*idx) s = m+1;
else e = m-1;
}
return e;
}
int vbs(vector<int> &st, int val) {
int s = 0, e = (int)st.size()-1;
while(s<=e) {
int m = (s+e)>>1;
if (value[st[m]]<val) s = m+1;
else e = m-1;
}
return s;
}
int query(int b) {
if (b==a) return 0;
if (b>a) {
int idx =vbs(lst,value[rst[ibs(rst,b,1)]]);
return b-((idx==lst.size())?-1:lst[idx])-1;
}
int idx = vbs(rst,value[lst[ibs(lst,b,-1)]]);
return ((idx==rst.size())?n:rst[idx])-b-1;
}
int main() {
int i;
//freopen("input","r",stdin);
scanf("%d%d",&n,&a);
a--;
for (i=0;i<n;i++) scanf("%d",&arr[i]);
com(arr,value);
maxv = n-1;
for (i=0;i<n;i++) ord[value[i]] = i;
for (i=a-1;i>=0;i--) push(lst,i);
for (i=a+1;i<n;i++) push(rst,i);
scanf("%d",&q);
for (i=0;i<n+q;i++) pre[i] = i-1;
for (i=0;i<q;i++) {
char que[3];
scanf("%s",que);
if (que[0]=='E') {
int a, b;
scanf("%d%d",&a,&b);
upd(--a,b);
}
else {
int b;
scanf("%d",&b);
printf("%d\n",query(--b));
}
}
return 0;
}
Compilation message (stderr)
cake.cpp: In function 'void deb()':
cake.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lst.size();i++) {
^
cake.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<rst.size();i++) {
^
cake.cpp: In function 'void upd(int, int)':
cake.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<can.size();i++) {
^
cake.cpp: In function 'int query(int)':
cake.cpp:108:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
return b-((idx==lst.size())?-1:lst[idx])-1;
^
cake.cpp:111:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
return ((idx==rst.size())?n:rst[idx])-b-1;
^
cake.cpp: In function 'int main()':
cake.cpp:119:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&a);
^
cake.cpp:121:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i=0;i<n;i++) scanf("%d",&arr[i]);
^
cake.cpp:127:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
cake.cpp:131:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",que);
^
cake.cpp:134:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
^
cake.cpp:139:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&b);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |