Submission #770755

#	Time	Username	Problem	Language	Result	Execution time	Memory
770755		Ahmed57	Cake 3 (JOI19_cake3)	C++17	0 / 100	240 ms	420 KiB

cake3

#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 (stderr)

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 cake3.cpp:4:
cake3.cpp: In function 'int main()':
cake3.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);
      |                    ~~~~~~~~^~~
cake3.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);
      |                ~~~~~~~~^~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76