| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 224773 |
2020-04-18T18:50:45 Z |
brcode |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
8428 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 = 0;
// cout<<123<<" "<<temp<<endl;
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<<1234<<" "<<curr<<" "<<val<<endl;
//cout<<1234<<" "<<val<<" "<<rev[curr]<<endl;
for(int i=val;i>rev[curr];i--){
// cout<<123<<" "<<ranks[2]<<" "<<i-1<<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=rev[curr]+1;i<=val;i++){
ranks[i-1] = ranks[i];
rev[ranks[i]] = i-1;
//cout<<(i-1)<<" "<<ranks[i-1]<<endl;
}
ranks[val] = curr;
rev[curr] = val;
// cout<<endl;
/* for(int i=1;i<=n;i++){
// cout<<rev[i]<<" ";
}
// cout<<endl;
for(int i=1;i<=n;i++){
// cout<<ranks[i]<<" ";
}*/
//cout<<endl;
if(curr==k){
continue;
}
if(curr<k){
segl.update(1,1,k-1,curr,val);
}else{
segr.update(1,k+1,n,curr,val);
}
}
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:100:9: warning: unused variable 'ub' [-Wunused-variable]
int ub = max(1,n-10);
^~
| # |
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 |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
71 ms |
384 KB |
Output is correct |
| 5 |
Execution timed out |
2069 ms |
1016 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2089 ms |
896 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2097 ms |
1912 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2091 ms |
1272 KB |
Time limit exceeded |
| 4 |
Correct |
406 ms |
1784 KB |
Output is correct |
| 5 |
Execution timed out |
2084 ms |
1408 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2080 ms |
1416 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2085 ms |
1408 KB |
Time limit exceeded |
| 8 |
Correct |
444 ms |
2168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1152 ms |
4872 KB |
Output is correct |
| 2 |
Correct |
564 ms |
4492 KB |
Output is correct |
| 3 |
Correct |
373 ms |
4508 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Execution timed out |
2050 ms |
8264 KB |
Time limit exceeded |
| 6 |
Correct |
1313 ms |
8072 KB |
Output is correct |
| 7 |
Correct |
411 ms |
7896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2077 ms |
1136 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2090 ms |
1068 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2074 ms |
2168 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2082 ms |
2192 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2086 ms |
1516 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2078 ms |
2808 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2075 ms |
1152 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2090 ms |
3704 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2075 ms |
7416 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2077 ms |
1528 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2071 ms |
1344 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2077 ms |
6648 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2084 ms |
8428 KB |
Time limit exceeded |
