oj.uz

Submission #1110566

# Submission time Handle Problem Language Result Execution time Memory
1110566 2024-11-09T21:51:55 Z vladilius Secret (JOI14_secret) C++17
100 / 100
 319 ms 4436 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

vector<vector<int>> x;
vector<int> a;
int n, lg;

void build(int d, int l, int r){
    if (l == r) return;
    int m = (l + r) / 2;
    x[d][m] = a[m];
    for (int i = m - 1; i >= l; i--){
        x[d][i] = Secret(a[i], x[d][i + 1]);
    }
    x[d][m + 1] = a[m + 1];
    for (int i = m + 2; i <= r; i++){
        x[d][i] = Secret(x[d][i - 1], a[i]);
    }
    
    build(d + 1, l, m);
    build(d + 1, m + 1, r);
}

void Init(int ns, int A[]){
    n = ns;
    a.resize(n + 1);
    for (int i = 1; i <= n; i++){
        a[i] = A[i - 1];
    }
    
    lg = log2(n);
    x.resize(lg + 1);
    for (int i = 0; i <= lg; i++){
        x[i].resize(n + 1);
    }
    build(0, 1, n);
}

int get(int d, int tl, int tr, int& l, int& r){
    int tm = (tl + tr) / 2;
    if (l <= tm && tm < r){
        return Secret(x[d][l], x[d][r]);
    }
    return (r <= tm) ? get(d + 1, tl, tm, l, r) : get(d + 1, tm + 1, tr, l, r);
}

int Query(int l, int r){
    l++; r++;
    if (l == r) return a[l];
    return get(0, 1, n, l, r);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 2640 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 85 ms 2640 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 89 ms 2640 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 317 ms 4276 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 319 ms 4372 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 309 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 300 ms 4388 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 306 ms 4280 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 310 ms 4424 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 307 ms 4424 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1