| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 224742 |
2020-04-18T17:24:23 Z |
brcode |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
9536 KB |
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,k;
const int MAXN = 5e5+5;
pair<int,int> arr[MAXN];
int ranks[MAXN];
int rev[MAXN];
struct segmenttree{
int seg[4*MAXN];
void build(int curr,int l,int r){
if(l==r){
seg[curr] = rev[l];
return;
}
int mid = (l+r)/2;
build(2*curr,l,mid);
build(2*curr+1,mid+1,r);
seg[curr] = max(seg[2*curr],seg[2*curr+1]);
}
int query(int curr,int l,int r,int tl,int tr){
if(l>tr||r<tl){
return -1e9;
}
if(tl<=l && r<=tr){
return seg[curr];
}
int mid = (l+r)/2;
return max(query(2*curr,l,mid,tl,tr),query(2*curr+1,mid+1,r,tl,tr));
}
int lmost(int curr,int l,int r,int val){
if(seg[curr]<val){
return r+1;
}
if(l==r){
return l;
}
int mid = (l+r)/2;
if(seg[2*curr]>val){
return lmost(2*curr,l,mid,val);
}else if(seg[2*curr+1]>val){
return lmost(2*curr+1,mid+1,r,val);
}else{
return r+1;
}
}
int rmost(int curr,int l,int r,int val){
if(seg[curr]<val){
return l-1;
}
if(l==r){
return l;
}
int mid = (l+r)/2;
if(seg[2*curr+1]>val){
return rmost(2*curr+1,mid+1,r,val);
}else if(seg[2*curr]>val){
return rmost(2*curr,l,mid,val);
}else{
return l-1;
}
}
void update(int curr,int l,int r,int ind ,int val){
if(l==r){
seg[curr] = val;
return;
}
int mid = (l+r)/2;
if(ind<=mid){
update(2*curr,l,mid,ind,val);
}else{
update(2*curr+1,mid+1,r,ind,val);
}
seg[curr] = max(seg[2*curr],seg[2*curr+1]);
}
} segl,segr;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>arr[i].first;
arr[i].second = i;
}
sort(arr+1,arr+n+1);
for(int i=1;i<=n;i++){
ranks[i] = arr[i].second;
rev[arr[i].second] = i;//what rank is ith position
}
if(k!=1){
segl.build(1,1,k-1);
}
if(k!=n){
segr.build(1,k+1,n);
}
int q;
cin>>q;
int ub = max(1,n-10);
while(q--){
char s;
cin>>s;
if(s=='F'){
int x;
cin>>x;
if(x==k){
cout<<0<<endl;
continue;
}
if(x<k){
int temp = segl.query(1,1,k-1,x,k-1);
int temp2 = n+1;
if(temp!=n){
temp2 = segr.lmost(1,k+1,n,temp);
}
//cout<<x<<" "<<temp2<<endl;
cout<<temp2-x-1<<endl;
}else{
int temp = segr.query(1,k+1,n,k+1,x);
int temp2 = 1;
if(temp!=n){
temp2 = segl.rmost(1,1,k-1,temp);
}
// cout<<123<<" "<<temp2<<endl;
cout<<x-temp2-1<<endl;
}
}else{
int curr,val;
cin>>curr>>val;
//cout<<curr<<" "<<val<<endl;
val = n-val+1;
// cout<<curr<<" "<<val<<endl;
// cout<<rev[curr]<<endl;
for(int i=val;i>=min(n-rev[curr],ub);i--){
// cout<<123<<" "<<i<<" "<<ranks[i]<<endl;
//cout<<1234<<" "<<i<<" "<<ranks[i]<<" "<<min(rev[curr],min(10,n))<<endl;
if(ranks[i] == k){
continue;
}
if(ranks[i]<k){
segl.update(1,1,k-1,ranks[i],i-1);
}else{
segr.update(1,k+1,n,ranks[i],i-1);
}
}
for(int i=val;i>=min(n-rev[curr],ub);i--){
ranks[i-1] = ranks[i];
rev[ranks[i-1]] = i-1;
}
ranks[val] = curr;
rev[curr] = val;
if(curr==k){
continue;
}
if(curr<k){
segl.update(1,1,k-1,curr,val);
}else{
segr.update(1,k+1,n,curr,val);
}
}
}
}
| # |
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 |
Execution timed out |
2097 ms |
1016 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2087 ms |
1056 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2087 ms |
1024 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2095 ms |
1144 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2087 ms |
1408 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2094 ms |
1528 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2082 ms |
1528 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2094 ms |
1528 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
607 ms |
4912 KB |
Output isn't correct |
| 2 |
Incorrect |
682 ms |
4856 KB |
Output isn't correct |
| 3 |
Incorrect |
627 ms |
4856 KB |
Output isn't correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
912 ms |
9464 KB |
Output isn't correct |
| 6 |
Incorrect |
1236 ms |
9536 KB |
Output isn't correct |
| 7 |
Incorrect |
1197 ms |
9436 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2083 ms |
1068 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2091 ms |
1280 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2085 ms |
2320 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2098 ms |
2176 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2095 ms |
1312 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2070 ms |
2936 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2080 ms |
1296 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2099 ms |
3704 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2092 ms |
8056 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2094 ms |
1272 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2098 ms |
1272 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2089 ms |
6904 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2089 ms |
9080 KB |
Time limit exceeded |
