| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 224762 |
2020-04-18T18:16:01 Z |
brcode |
Cake (CEOI14_cake) |
C++14 |
|
1384 ms |
13816 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<<rev[curr]<<endl;
for(int i=val;i>=max(n-rev[curr],ub);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){
segl.update(1,1,k-1,ranks[i],i-1);
}else{
segr.update(1,k+1,n,ranks[i],i-1);
}
}
for(int i=max(n-rev[curr],ub)+1;i<=val;i++){
ranks[i-1] = ranks[i];
rev[ranks[i-1]] = i-1;
//cout<<(i-1)<<" "<<ranks[i-1]<<endl;
}
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 |
Incorrect |
662 ms |
4856 KB |
Output isn't correct |
| 2 |
Incorrect |
677 ms |
4960 KB |
Output isn't correct |
| 3 |
Incorrect |
662 ms |
5032 KB |
Output isn't correct |
| 4 |
Correct |
694 ms |
4984 KB |
Output is correct |
| 5 |
Incorrect |
688 ms |
5532 KB |
Output isn't correct |
| 6 |
Incorrect |
765 ms |
5800 KB |
Output isn't correct |
| 7 |
Incorrect |
715 ms |
5672 KB |
Output isn't correct |
| 8 |
Correct |
754 ms |
5880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
335 ms |
3576 KB |
Output isn't correct |
| 2 |
Incorrect |
326 ms |
3684 KB |
Output isn't correct |
| 3 |
Incorrect |
321 ms |
3448 KB |
Output isn't correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
418 ms |
7160 KB |
Output isn't correct |
| 6 |
Incorrect |
417 ms |
7288 KB |
Output isn't correct |
| 7 |
Incorrect |
428 ms |
6904 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
110 ms |
632 KB |
Output isn't correct |
| 2 |
Incorrect |
119 ms |
888 KB |
Output isn't correct |
| 3 |
Incorrect |
207 ms |
2552 KB |
Output isn't correct |
| 4 |
Incorrect |
208 ms |
2680 KB |
Output isn't correct |
| 5 |
Incorrect |
312 ms |
1272 KB |
Output isn't correct |
| 6 |
Incorrect |
391 ms |
3960 KB |
Output isn't correct |
| 7 |
Incorrect |
440 ms |
2680 KB |
Output isn't correct |
| 8 |
Incorrect |
381 ms |
5112 KB |
Output isn't correct |
| 9 |
Incorrect |
1384 ms |
12884 KB |
Output isn't correct |
| 10 |
Incorrect |
1037 ms |
4860 KB |
Output isn't correct |
| 11 |
Incorrect |
1104 ms |
6520 KB |
Output isn't correct |
| 12 |
Incorrect |
1272 ms |
12024 KB |
Output isn't correct |
| 13 |
Incorrect |
1235 ms |
13816 KB |
Output isn't correct |
