oj.uz

Submission #677413

# Submission time Handle Problem Language Result Execution time Memory
677413 2023-01-03T08:35:07 Z vjudge1 Cake (CEOI14_cake) C++17
0 / 100
 1526 ms 17464 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={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++){
                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:47: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]
   47 |             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 459 ms 8896 KB Output isn't correct
2 Incorrect 259 ms 4812 KB Output isn't correct
3 Incorrect 297 ms 8920 KB Output isn't correct
4 Correct 169 ms 8888 KB Output is correct
5 Incorrect 438 ms 9228 KB Output isn't correct
6 Incorrect 393 ms 5232 KB Output isn't correct
7 Incorrect 307 ms 9200 KB Output isn't correct
8 Correct 166 ms 17464 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 352 ms 5132 KB Output isn't correct
2 Incorrect 351 ms 5072 KB Output isn't correct
3 Incorrect 339 ms 5104 KB Output isn't correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 470 ms 10952 KB Output isn't correct
6 Incorrect 316 ms 10928 KB Output isn't correct
7 Incorrect 278 ms 10692 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 1088 KB Output isn't correct
2 Incorrect 73 ms 1104 KB Output isn't correct
3 Incorrect 164 ms 3868 KB Output isn't correct
4 Incorrect 212 ms 3856 KB Output isn't correct
5 Incorrect 220 ms 2788 KB Output isn't correct
6 Incorrect 335 ms 7056 KB Output isn't correct
7 Incorrect 310 ms 3116 KB Output isn't correct
8 Incorrect 149 ms 11276 KB Output isn't correct
9 Incorrect 1526 ms 16036 KB Output isn't correct
10 Incorrect 718 ms 5680 KB Output isn't correct
11 Incorrect 1081 ms 10692 KB Output isn't correct
12 Incorrect 1518 ms 14272 KB Output isn't correct
13 Incorrect 1458 ms 14820 KB Output isn't correct