oj.uz

Submission #677411

# Submission time Handle Problem Language Result Execution time Memory
677411 2023-01-03T08:30:53 Z vjudge1 Cake (CEOI14_cake) C++17
0 / 100
 1441 ms 17708 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;
            map<int,bool>mp;
            while(--y){
                if(mp[pq.top().second]){
                    pq.pop();
                    y++;
                    continue;
                }
                mp[pq.top().second]=1;
                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(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:58: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]
   58 |             for(int i=0;i<dq.size();i++){
      |                         ~^~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 410 ms 8956 KB Output isn't correct
2 Incorrect 221 ms 8988 KB Output isn't correct
3 Incorrect 253 ms 8956 KB Output isn't correct
4 Correct 130 ms 8852 KB Output is correct
5 Incorrect 405 ms 9412 KB Output isn't correct
6 Incorrect 356 ms 5184 KB Output isn't correct
7 Incorrect 259 ms 9240 KB Output isn't correct
8 Correct 143 ms 17708 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 312 ms 5284 KB Output isn't correct
2 Incorrect 335 ms 5072 KB Output isn't correct
3 Incorrect 317 ms 5072 KB Output isn't correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 430 ms 11164 KB Output isn't correct
6 Incorrect 315 ms 10944 KB Output isn't correct
7 Incorrect 277 ms 10660 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 1124 KB Output isn't correct
2 Incorrect 69 ms 1116 KB Output isn't correct
3 Incorrect 149 ms 3860 KB Output isn't correct
4 Incorrect 172 ms 3796 KB Output isn't correct
5 Incorrect 203 ms 2776 KB Output isn't correct
6 Incorrect 306 ms 7000 KB Output isn't correct
7 Incorrect 293 ms 3048 KB Output isn't correct
8 Incorrect 130 ms 11316 KB Output isn't correct
9 Incorrect 1441 ms 16068 KB Output isn't correct
10 Incorrect 686 ms 5496 KB Output isn't correct
11 Incorrect 1006 ms 10520 KB Output isn't correct
12 Incorrect 1412 ms 14296 KB Output isn't correct
13 Incorrect 1309 ms 15104 KB Output isn't correct