oj.uz

Submission #677412

# Submission time Handle Problem Language Result Execution time Memory
677412 2023-01-03T08:34:51 Z vjudge1 Cake (CEOI14_cake) C++17
0 / 100
 1560 ms 17456 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 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 457 ms 8864 KB Output isn't correct
2 Incorrect 252 ms 4764 KB Output isn't correct
3 Incorrect 294 ms 9028 KB Output isn't correct
4 Correct 149 ms 8888 KB Output is correct
5 Incorrect 470 ms 9452 KB Output isn't correct
6 Incorrect 393 ms 5116 KB Output isn't correct
7 Incorrect 298 ms 9244 KB Output isn't correct
8 Correct 157 ms 17456 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 338 ms 5160 KB Output isn't correct
2 Incorrect 354 ms 5068 KB Output isn't correct
3 Incorrect 332 ms 5072 KB Output isn't correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 459 ms 10864 KB Output isn't correct
6 Incorrect 317 ms 10956 KB Output isn't correct
7 Incorrect 288 ms 10740 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 1092 KB Output isn't correct
2 Incorrect 72 ms 1160 KB Output isn't correct
3 Incorrect 163 ms 3772 KB Output isn't correct
4 Incorrect 244 ms 3804 KB Output isn't correct
5 Incorrect 218 ms 2760 KB Output isn't correct
6 Incorrect 338 ms 6952 KB Output isn't correct
7 Incorrect 327 ms 3116 KB Output isn't correct
8 Incorrect 152 ms 11204 KB Output isn't correct
9 Incorrect 1554 ms 15804 KB Output isn't correct
10 Incorrect 730 ms 5560 KB Output isn't correct
11 Incorrect 1142 ms 10496 KB Output isn't correct
12 Incorrect 1560 ms 14276 KB Output isn't correct
13 Incorrect 1496 ms 14780 KB Output isn't correct