oj.uz

Submission #915879

# Submission time Handle Problem Language Result Execution time Memory
915879 2024-01-24T20:28:14 Z AlphaMale06 Secret (JOI14_secret) C++14
100 / 100
 374 ms 7520 KB 
#include "secret.h"

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second

vector<pair<int, pair<int, int>>> vc;
int b[1001];
int vals[1001][1001];
int m;

void solve(int l, int r, int L, int R, int lvl){
    if(l+1>=r)return;
    int mid=l+r>>1;
    vc.push_back({mid, {lvl, 0}});
    vc.push_back({mid+1, {lvl, 1}});
    vals[mid][mid]=b[mid];
    vals[mid+1][mid+1]=b[mid+1];
    for(int i=mid-1; i>=L; i--){
        vals[mid][i]=Secret(b[i], vals[mid][i+1]);
    }
    for(int i=mid+2; i<=R; i++){
        vals[mid+1][i]=Secret(vals[mid+1][i-1], b[i]);
    }
    solve(l, mid-1, L, mid-1, lvl+1);
    solve(mid+2, r, mid+2, R, lvl+1);
}

void Init(int n, int a[]) {
    m=n;
    for(int i=0; i<n; i++)b[i]=a[i];
    solve(0, n-1, 0, n-1, 1);
    sort(vc.begin(), vc.end());
}

int Query(int l, int r) {
    if(l==r)return b[l];
    if(l==r-1)return Secret(b[l], b[l+1]);
    int mn=1e9;
    int p[2]={-1, -1};
    for(auto e : vc){
        if(e.F>=l && e.F<=r){
            if(e.S.F<mn){
                p[0]=p[1]=-1;
                mn=e.S.F;
                p[e.S.S]=e.F;
            }
            else if(e.S.F==mn){
                p[e.S.S]=e.F;
            }
        }
    }
    if(p[0]==-1)return vals[p[1]][r];
    if(p[1]==-1)return vals[p[0]][l];
    else{
        return Secret(vals[p[0]][l], vals[p[1]][r]);
    }
}

Compilation message

secret.cpp: In function 'void solve(int, int, int, int, int)':
secret.cpp:16:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 6756 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 109 ms 6760 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 104 ms 6736 KB Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1
4 Correct 361 ms 7512 KB Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1
5 Correct 360 ms 7504 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
6 Correct 357 ms 7512 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
7 Correct 361 ms 7420 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 374 ms 7520 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 363 ms 7508 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 367 ms 7512 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1