Submission #914340

#	Time	Username	Problem	Language	Result	Execution time	Memory
914340		sverma22	Secret (JOI14_secret)	C++17	0 / 100	378 ms	4844 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"

using namespace std; 

// #define int int64_t

struct Info {
    int L, R, M; 
    vector<int> pre; 
    vector<int> suff; 
}; 

map<int, Info> info_map; // layer ... 
vector<int> a; 
int N; 

// int Secret(int x, int y) {
//     return min(x, y); 
// }

void dvc(int l, int r, int layer = 1) {
    if(l == r) {
        return; 
    }

    int m = (l + r) / 2; 
    info_map[layer].pre.resize(m - l + 1); 
    info_map[layer].suff.resize(r - m); // (r - (m + 1) + 1)

    info_map[layer].pre[m - l] = a[m]; 
    for(int i = m - 1; i >= l; i--) info_map[layer].pre[i - l] = Secret(a[i], info_map[layer].pre[i - l + 1]);

    info_map[layer].suff[0] = a[m + 1]; 
    for(int i = m + 2; i <= r; i++) info_map[layer].suff[i - m - 1] = Secret(a[i], info_map[layer].suff[i - m - 2]); 

    info_map[layer].L = l; 
    info_map[layer].R = r; 
    info_map[layer].M = m; 

    dvc(l, m, 2 * layer); 
    dvc(m + 1, r, 2 * layer + 1); 
}


void Init(int n, int A[]) {
    N = n; 
    a.resize(n); 
    for(int i = 0; i < n; i++) a[i] = A[i]; 

    dvc(0, n - 1); 
}



int Query(int L, int R) {
    // FIND THE CORRECT LAYER 
    if(L == R) return a[L]; 
    int layer = 1; 
    while(true) {
        if(L <= info_map[layer].M && info_map[layer].M <= R) {
            return Secret(info_map[layer].pre[L - info_map[layer].L], info_map[layer].suff[R - info_map[layer].M - 1]); 
        } else if(L >= info_map[layer].M) {
            layer = 2 * layer + 1; // go to right child
        } else {
            layer = 2 * layer; // go to left child ... 
        }
    }

    return 0; 
}


// signed main() {
//     int A[8] = {2, 4, 3, 1, 7, 6, 2, 4}; 
//     Init(8, A); 

//     for(int i = 1; i <= 7; i++) {
//         cout << info_map[i].L << ' ' << info_map[i].R << '\n';
//     }

//     vector<pair<int, int> > qs = {{0, 0}, {0, 1}, {1, 2}, {3, 5}, {5, 7}, {2, 5}}; 

//     for(auto [a, b] : qs) {
//         cout << Query(a, b) << '\n';
//     }

// }

• Subtask 1: 0 / 100