Submission #915878

#	Time	Username	Problem	Language	Result	Execution time	Memory
915878		AlphaMale06	Secret (JOI14_secret)	C++14	6 / 100	541 ms	8332 KiB

secret

#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 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>=0; i--){
        vals[mid][i]=Secret(b[i], vals[mid][i+1]);
    }
    for(int i=mid+2; i<m; i++){
        vals[mid+1][i]=Secret(vals[mid+1][i-1], b[i]);
    }
    solve(l, mid-1, lvl+1);
    solve(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, 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 (stderr)

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

• Subtask 1: 6 / 100