| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 770756 |
2023-07-01T21:29:28 Z |
Ahmed57 |
Cake (CEOI14_cake) |
C++17 |
|
1982 ms |
25168 KB |
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
int arr[250001];
long long seg[1000001];
void build(int p,int l,int r){
if(l==r){
seg[p] = arr[l];
return ;
}
int md =(l+r)/2;
build(p*2,l,md);build(p*2+1,md+1,r);
seg[p] = max(seg[p*2],seg[p*2+1]);
}
long long query(int p,int l,int r,int lq,int rq){
if(l>=lq&&r<=rq)return seg[p];
if(l>rq||r<lq)return -1e9;
int md = (l+r)/2;
return max(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
void update(int p,int l,int r,int ns){
if(seg[p]<ns)return ;
if(l==r){
seg[p]++;
return ;
}
int md = (l+r)/2;
update(p*2,l,md,ns);update(p*2+1,md+1,r,ns);
seg[p] = max(seg[p*2],seg[p*2+1]);
}
void update2(int p,int l,int r,int idx,int val){
if(l==r){
seg[p] = val;
return ;
}
int md = (l+r)/2;
if(idx<=md)update2(p*2,l,md,idx,val);
else update2(p*2+1,md+1,r,idx,val);
seg[p] = max(seg[p*2],seg[p*2+1]);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
ordered_set s;
int n,a;cin>>n>>a;
for(int i = 1;i<=n;i++){
cin>>arr[i];
s.insert(arr[i]);
}
build(1,1,n);
int q;cin>>q;
while(q--){
char c;cin>>c;
if(c=='F'){
int ind;cin>>ind;
if(ind==a){
cout<<0<<endl;
continue;
}
long long val = 0;
if(ind<a){
val= query(1,1,n,ind,a-1);
}else{
val = query(1,1,n,a+1,ind);
}
long long an = abs(ind-a);
if(ind<a){
int l = a+1 , r = n , ans = a;
while(l<=r){
int mid = (l+r)/2;
if(query(1,1,n,a+1,mid)<=val){
ans = mid;
l = mid+1;
}else r = mid-1;
}
an+=abs(ans-a);
}else{
int l = 1 , r = a-1 , ans = a;
while(l<=r){
int mid = (l+r)/2;
if(query(1,1,n,mid,a-1)<=val){
ans = mid;
r = mid-1;
}else l = mid+1;
}
an+=abs(a-ans);
}
cout<<an<<endl;
}else{
int idx,rnk;
cin>>idx>>rnk;
int la = 1e9;
for(int j = n-1;j>(n-rnk);j--){
auto val = s.find_by_order(j);
la = *val;
s.erase(val);
s.insert(la+1);
}
int z = query(1,1,n,idx,idx);
assert(z<la);
assert(s.size()==n);
long long nee = (la==1e9?(*s.find_by_order(s.size()-1))+1:la);
auto it = s.lower_bound(z);
s.erase(it);
s.insert(nee);
update(1,1,n,la);
update2(1,1,n,idx,nee);
assert(nee<1e9);
assert(s.size()==n);
}
}
}
Compilation message
In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
from cake.cpp:4:
cake.cpp: In function 'int main()':
cake.cpp:106:28: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::detail::tree_traits<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
106 | assert(s.size()==n);
| ~~~~~~~~^~~
cake.cpp:114:24: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::detail::tree_traits<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
114 | assert(s.size()==n);
| ~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
9 ms |
460 KB |
Output is correct |
| 5 |
Correct |
26 ms |
1248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
649 ms |
5388 KB |
Output is correct |
| 2 |
Correct |
415 ms |
5428 KB |
Output is correct |
| 3 |
Correct |
492 ms |
5452 KB |
Output is correct |
| 4 |
Correct |
269 ms |
5428 KB |
Output is correct |
| 5 |
Correct |
771 ms |
6684 KB |
Output is correct |
| 6 |
Correct |
647 ms |
7096 KB |
Output is correct |
| 7 |
Correct |
498 ms |
6836 KB |
Output is correct |
| 8 |
Correct |
351 ms |
7112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
488 ms |
9348 KB |
Output is correct |
| 2 |
Correct |
399 ms |
9204 KB |
Output is correct |
| 3 |
Correct |
356 ms |
9128 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
519 ms |
20152 KB |
Output is correct |
| 6 |
Correct |
594 ms |
20208 KB |
Output is correct |
| 7 |
Correct |
532 ms |
20056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
924 KB |
Output is correct |
| 2 |
Correct |
102 ms |
1220 KB |
Output is correct |
| 3 |
Correct |
221 ms |
5092 KB |
Output is correct |
| 4 |
Correct |
234 ms |
4940 KB |
Output is correct |
| 5 |
Correct |
285 ms |
1892 KB |
Output is correct |
| 6 |
Correct |
441 ms |
6804 KB |
Output is correct |
| 7 |
Correct |
367 ms |
3108 KB |
Output is correct |
| 8 |
Correct |
274 ms |
9932 KB |
Output is correct |
| 9 |
Correct |
1982 ms |
24976 KB |
Output is correct |
| 10 |
Correct |
975 ms |
5320 KB |
Output is correct |
| 11 |
Correct |
1343 ms |
7436 KB |
Output is correct |
| 12 |
Correct |
1926 ms |
22084 KB |
Output is correct |
| 13 |
Correct |
1894 ms |
25168 KB |
Output is correct |
