oj.uz

Submission #914341

# Submission time Handle Problem Language Result Execution time Memory
914341 2024-01-21T17:03:23 Z sverma22 Secret (JOI14_secret) C++17
0 / 100
 373 ms 4688 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 2644 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 809782271.
2 Incorrect 111 ms 2904 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 68749376.
3 Incorrect 97 ms 2724 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 136349820.
4 Incorrect 367 ms 4688 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 650789536.
5 Incorrect 373 ms 4388 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 377506838.
6 Incorrect 366 ms 4532 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 61461050.
7 Incorrect 363 ms 4436 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 687550570.
8 Incorrect 369 ms 4516 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 145923264.
9 Incorrect 362 ms 4524 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 18757135.
10 Incorrect 368 ms 4532 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 70590726.