oj.uz

Submission #677410

# Submission time Handle Problem Language Result Execution time Memory
677410 2023-01-03T08:24:21 Z vjudge1 Cake (CEOI14_cake) C++17
0 / 100
 1497 ms 22480 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)));
    int arr[n];
    for(auto &i:arr)cin>>i;
    for(int i=0;i<n;i++)seg[i+N]=arr[i];
    for(int i=N-1;i;i--)seg[i]=max(seg[i*2],seg[i*2+1]);
    priority_queue<pair<int,int>>pq;
    for(int i=0;i<n;i++)pq.push({arr[i],i});
    cin>>q;
    while(q--){
        char c;
        cin>>c;
        if(c=='E'){
            cin>>x>>y;
            deque<int>dq;
            while(--y){
                dq.push_back({pq.top().second});
                pq.pop();
            }
            {
                arr[x-1]=mx;
                pq.push({mx,x-1});
                int in=x-1+N;
                seg[in]=mx;
                in/=2;
                while(in){
                    seg[in]=max(seg[in*2],seg[in*2+1]);
                    in/=2;
                }
                mx++;
            }
            for(int i=0;i<dq.size();i++){
                arr[dq[i]]=mx;
                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(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:51: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]
   51 |             for(int i=0;i<dq.size();i++){
      |                         ~^~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 316 ms 13208 KB Output isn't correct
2 Incorrect 204 ms 13072 KB Output isn't correct
3 Incorrect 227 ms 13148 KB Output isn't correct
4 Correct 130 ms 13068 KB Output is correct
5 Incorrect 355 ms 13908 KB Output isn't correct
6 Incorrect 294 ms 22452 KB Output isn't correct
7 Incorrect 245 ms 22316 KB Output isn't correct
8 Correct 137 ms 22480 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 342 ms 6528 KB Output isn't correct
2 Incorrect 350 ms 6384 KB Output isn't correct
3 Incorrect 346 ms 6356 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Incorrect 489 ms 13560 KB Output isn't correct
6 Incorrect 324 ms 13372 KB Output isn't correct
7 Incorrect 348 ms 13172 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 1540 KB Output isn't correct
2 Incorrect 69 ms 1588 KB Output isn't correct
3 Incorrect 204 ms 4604 KB Output isn't correct
4 Incorrect 180 ms 4600 KB Output isn't correct
5 Incorrect 193 ms 3964 KB Output isn't correct
6 Incorrect 344 ms 8528 KB Output isn't correct
7 Incorrect 326 ms 4548 KB Output isn't correct
8 Incorrect 129 ms 13672 KB Output isn't correct
9 Incorrect 1497 ms 22220 KB Output isn't correct
10 Incorrect 645 ms 9188 KB Output isn't correct
11 Incorrect 1050 ms 14872 KB Output isn't correct
12 Incorrect 1416 ms 20136 KB Output isn't correct
13 Incorrect 1416 ms 22232 KB Output isn't correct