oj.uz

Submission #678217

# Submission time Handle Problem Language Result Execution time Memory
678217 2023-01-05T10:13:46 Z MrDeboo Cake (CEOI14_cake) C++17
0 / 100
 43 ms 16828 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'){
            assert(0);
            cin>>x>>y;
            deque<int>dq={x-1};
            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_back(pq.top().second);
                pq.pop();
            }
            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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1368 KB Execution killed with signal 6
2 Runtime error 3 ms 1496 KB Execution killed with signal 6
3 Runtime error 2 ms 1496 KB Execution killed with signal 6
4 Runtime error 3 ms 1496 KB Execution killed with signal 6
5 Runtime error 4 ms 2388 KB Execution killed with signal 6
6 Runtime error 5 ms 2452 KB Execution killed with signal 6
7 Runtime error 5 ms 2388 KB Execution killed with signal 6
8 Runtime error 5 ms 2388 KB Execution killed with signal 6

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 7624 KB Execution killed with signal 6
2 Runtime error 22 ms 7564 KB Execution killed with signal 6
3 Runtime error 16 ms 7572 KB Execution killed with signal 6
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 Runtime error 37 ms 16828 KB Execution killed with signal 6
6 Runtime error 40 ms 16784 KB Execution killed with signal 6
7 Runtime error 36 ms 16800 KB Execution killed with signal 6

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 756 KB Execution killed with signal 6
2 Runtime error 3 ms 1108 KB Execution killed with signal 6
3 Runtime error 10 ms 4176 KB Execution killed with signal 6
4 Runtime error 12 ms 4176 KB Execution killed with signal 6
5 Runtime error 1 ms 596 KB Execution killed with signal 6
6 Runtime error 11 ms 5964 KB Execution killed with signal 6
7 Runtime error 3 ms 1496 KB Execution killed with signal 6
8 Runtime error 15 ms 7604 KB Execution killed with signal 6
9 Runtime error 37 ms 16792 KB Execution killed with signal 6
10 Runtime error 1 ms 596 KB Execution killed with signal 6
11 Runtime error 8 ms 2260 KB Execution killed with signal 6
12 Runtime error 30 ms 14404 KB Execution killed with signal 6
13 Runtime error 43 ms 16824 KB Execution killed with signal 6