| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 224984 |
2020-04-19T07:40:00 Z |
brcode |
Cake (CEOI14_cake) |
C++14 |
|
1604 ms |
18552 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];
int cnt = -1e9;
struct segmenttree{
pair<int,int> seg[4*MAXN];
void build(int curr,int l,int r){
if(l==r){
seg[curr] = make_pair(rev[l],0);
if(seg[curr].first == n-11){
seg[curr].second = -1e9;
}
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]);
}
pair<int,int> query(int curr,int l,int r,int tl,int tr){
if(l>tr||r<tl){
return make_pair(-1e9,-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,pair<int,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,pair<int,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 ,pair<int,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-11);
while(q--){
char s;
cin>>s;
if(s=='F'){
int x;
cin>>x;
if(x==k){
cout<<0<<endl;
continue;
}
if(x<k){
auto temp = segl.query(1,1,k-1,x,k-1);
int temp2 = n+1;
if(temp.first!=n){
temp2 = segr.lmost(1,k+1,n,temp);
}
//cout<<x<<" "<<temp2<<endl;
cout<<temp2-x-1<<endl;
}else{
auto temp = segr.query(1,k+1,n,k+1,x);
int temp2 = 0;
// cout<<123<<" "<<temp<<endl;
if(temp.first!=n){
temp2 = segl.rmost(1,1,k-1,temp);
}
// cout<<123<<" "<<temp.first<<" "<<temp.second<<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>max(ub,rev[curr]);i--){
// cout<<123<<" "<<ranks[i]<<" "<<i-1<<endl;
//cout<<1234<<" "<<i<<" "<<ranks[i]<<" "<<min(rev[curr],min(10,n))<<endl;
if(ranks[i] == k){
continue;
}
if(ranks[i]<k){
if(i-1 == n-11){
cnt++;
segl.update(1,1,k-1,ranks[i],make_pair(i-1,cnt));
}else{
segl.update(1,1,k-1,ranks[i],make_pair(i-1,0));
}
}else{
if(i-1 == n-11){
cnt++;
segr.update(1,k+1,n,ranks[i],make_pair(i-1,cnt));
}else{
segr.update(1,k+1,n,ranks[i],make_pair(i-1,0));
}
}
}
for(int i=max(ub,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,make_pair(val,0));
}else{
segr.update(1,k+1,n,curr,make_pair(val,0));
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
6 ms |
384 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
19 ms |
512 KB |
Output is correct |
| 5 |
Correct |
34 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
614 ms |
5088 KB |
Output is correct |
| 2 |
Correct |
455 ms |
5240 KB |
Output is correct |
| 3 |
Correct |
584 ms |
5240 KB |
Output is correct |
| 4 |
Correct |
437 ms |
5240 KB |
Output is correct |
| 5 |
Correct |
631 ms |
5880 KB |
Output is correct |
| 6 |
Correct |
600 ms |
6288 KB |
Output is correct |
| 7 |
Correct |
621 ms |
6060 KB |
Output is correct |
| 8 |
Correct |
465 ms |
6264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
350 ms |
6008 KB |
Output is correct |
| 2 |
Correct |
345 ms |
5756 KB |
Output is correct |
| 3 |
Correct |
335 ms |
5840 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
433 ms |
11512 KB |
Output is correct |
| 6 |
Correct |
453 ms |
11616 KB |
Output is correct |
| 7 |
Correct |
419 ms |
11556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
133 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
243 ms |
3320 KB |
Output is correct |
| 4 |
Correct |
221 ms |
3320 KB |
Output is correct |
| 5 |
Correct |
348 ms |
1840 KB |
Output is correct |
| 6 |
Correct |
467 ms |
5148 KB |
Output is correct |
| 7 |
Correct |
504 ms |
3064 KB |
Output is correct |
| 8 |
Correct |
356 ms |
6520 KB |
Output is correct |
| 9 |
Correct |
1604 ms |
16576 KB |
Output is correct |
| 10 |
Correct |
1109 ms |
5292 KB |
Output is correct |
| 11 |
Correct |
1244 ms |
6832 KB |
Output is correct |
| 12 |
Correct |
1474 ms |
15304 KB |
Output is correct |
| 13 |
Correct |
1354 ms |
18552 KB |
Output is correct |
