| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 224778 |
2020-04-18T18:55:39 Z |
brcode |
Cake (CEOI14_cake) |
C++14 |
|
1286 ms |
9012 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>max(ub,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=max(ub+1,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);
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
511 ms |
640 KB |
Output isn't correct |
| 2 |
Correct |
438 ms |
640 KB |
Output is correct |
| 3 |
Incorrect |
503 ms |
640 KB |
Output isn't correct |
| 4 |
Correct |
470 ms |
672 KB |
Output is correct |
| 5 |
Incorrect |
560 ms |
1024 KB |
Output isn't correct |
| 6 |
Correct |
530 ms |
1024 KB |
Output is correct |
| 7 |
Incorrect |
532 ms |
1024 KB |
Output isn't correct |
| 8 |
Correct |
454 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
351 ms |
3576 KB |
Output isn't correct |
| 2 |
Correct |
341 ms |
3404 KB |
Output is correct |
| 3 |
Correct |
326 ms |
3340 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
431 ms |
6976 KB |
Output isn't correct |
| 6 |
Incorrect |
428 ms |
6976 KB |
Output isn't correct |
| 7 |
Correct |
423 ms |
6776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
111 ms |
608 KB |
Output isn't correct |
| 2 |
Incorrect |
121 ms |
632 KB |
Output isn't correct |
| 3 |
Incorrect |
218 ms |
1888 KB |
Output isn't correct |
| 4 |
Incorrect |
197 ms |
1916 KB |
Output isn't correct |
| 5 |
Incorrect |
307 ms |
888 KB |
Output isn't correct |
| 6 |
Incorrect |
393 ms |
2680 KB |
Output isn't correct |
| 7 |
Incorrect |
449 ms |
1144 KB |
Output isn't correct |
| 8 |
Incorrect |
298 ms |
2936 KB |
Output isn't correct |
| 9 |
Incorrect |
1286 ms |
8132 KB |
Output isn't correct |
| 10 |
Incorrect |
977 ms |
1740 KB |
Output isn't correct |
| 11 |
Incorrect |
1059 ms |
2436 KB |
Output isn't correct |
| 12 |
Incorrect |
1237 ms |
7288 KB |
Output isn't correct |
| 13 |
Incorrect |
1174 ms |
9012 KB |
Output isn't correct |
