oj.uz

Submission #678220

# Submission time Handle Problem Language Result Execution time Memory
678220 2023-01-05T10:15:25 Z MrDeboo Cake (CEOI14_cake) C++17
100 / 100
 1666 ms 18436 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>;
int seg[2000000];
int L,R,N;
int slv(int l=1,int r=N,int in=1){
    if(l>R||r<L)return 0;
    if(l>=L&&r<=R)return seg[in];
    int m=(l+r)/2;
    return max(slv(l,m,in*2),slv(m+1,r,in*2+1));
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int mx=1000000000,n,a,q,x,y;
    cin>>n>>a;
    N=exp2(ceil(log2(n)));
    priority_queue<pair<int,int>>pq;
    for(int i=0;i<n;i++){
        cin>>seg[i+N];
        pq.push({seg[i+N],i});
    }
    for(int i=N-1;i;i--)seg[i]=max(seg[i*2],seg[i*2+1]);
    cin>>q;
    while(q--){
        char c;
        cin>>c;
        if(c=='E'){
            cin>>x>>y;
            deque<int>dq;
            map<int,bool>mp;
            mp[x-1]=1;
            while(--y){
                if(mp[pq.top().second]){
                    pq.pop();
                    y++;
                    continue;
                }
                mp[pq.top().second]=1;
                dq.push_front(pq.top().second);
                pq.pop();
            }
            dq.push_front(x-1);
            for(int i=0;i<dq.size();i++){
                int in=dq[i]+N;
                seg[in]=mx;
                in/=2;
                while(in){
                    seg[in]=max(seg[in*2],seg[in*2+1]);
                    in/=2;
                }
                pq.push({mx++,dq[i]});
            }
        }else{
            cin>>x;
            if(x==a){cout<<0<<endl;continue;}
            if(a==1||a==n){cout<<abs(a-x)<<endl;continue;}
            if(a<x){
                L=a+1,R=x;
                int k=slv();
                R=a-1;
                int l=1,r=a-1,f=a;
                while(l<=r){
                    L=(l+r)/2;
                    if(slv()>k)l=L+1;
                    else{
                        f=L;
                        r=L-1;
                    }
                }
                cout<<x-f<<endl;
            }else{
                L=x,R=a-1;
                int k=slv();
                L=a+1;
                int l=a+1,r=n,f=a;
                while(l<=r){
                    R=(l+r)/2;
                    if(slv()>k)r=R-1;
                    else{
                        f=R;
                        l=R+1;
                    }
                }
                cout<<f-x<<endl;
            }
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:48:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for(int i=0;i<dq.size();i++){
      |                         ~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 7 ms 468 KB Output is correct
5 Correct 25 ms 988 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 4760 KB Output is correct
2 Correct 266 ms 8760 KB Output is correct
3 Correct 284 ms 8828 KB Output is correct
4 Correct 161 ms 8824 KB Output is correct
5 Correct 447 ms 9016 KB Output is correct
6 Correct 403 ms 4916 KB Output is correct
7 Correct 309 ms 17244 KB Output is correct
8 Correct 165 ms 17324 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 5036 KB Output is correct
2 Correct 322 ms 4348 KB Output is correct
3 Correct 321 ms 4404 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 480 ms 9672 KB Output is correct
6 Correct 333 ms 9756 KB Output is correct
7 Correct 312 ms 9508 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 1044 KB Output is correct
2 Correct 101 ms 1084 KB Output is correct
3 Correct 179 ms 3432 KB Output is correct
4 Correct 187 ms 3504 KB Output is correct
5 Correct 225 ms 2768 KB Output is correct
6 Correct 317 ms 6376 KB Output is correct
7 Correct 315 ms 2980 KB Output is correct
8 Correct 160 ms 10488 KB Output is correct
9 Correct 1531 ms 18436 KB Output is correct
10 Correct 734 ms 5608 KB Output is correct
11 Correct 1064 ms 10364 KB Output is correct
12 Correct 1666 ms 17284 KB Output is correct
13 Correct 1409 ms 17624 KB Output is correct