oj.uz

Submission #952298

# Submission time Handle Problem Language Result Execution time Memory
952298 2024-03-23T13:51:57 Z Em1L Secret (JOI14_secret) C++17
100 / 100
 398 ms 8440 KB 
#include <bits/stdc++.h>
#include "secret.h"

std::vector < std::vector < int > > sum;
std::vector < int > a;

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

void Divide(int lx, int rx) {
    if (lx == rx) {
        sum[lx][lx] = a[lx];
        return;
    }

    if (lx > rx)
        return;

    int m = (lx + rx) / 2;

    sum[m][m] = a[m];
    sum[m + 1][m + 1] = a[m + 1];

    for (int i = m - 1; i >= lx; i--)
        sum[i][m] = Secret(a[i], sum[i + 1][m]);

    for (int i = m + 2; i <= rx; i++)
        sum[m + 1][i] = Secret(sum[m + 1][i - 1], a[i]);

    Divide(lx, m - 1);
    Divide(m + 1, rx);
}

int Get(int lx, int rx, int l, int r) {
    int m = (lx + rx) / 2;

    if (l <= m && m + 1 <= r) {
        return Secret(sum[l][m], sum[m + 1][r]);
    }

    if (r <= m)
        return Get(lx, m - 1, l, r);

    return Get(m + 1, rx, l, r);
}

void Init(int N, int A[]) {
    sum.resize(N, std::vector < int >(N));
    a.resize(N);

    for (int i = 0; i < N; i++)
        a[i] = A[i];

    Divide(0, N - 1);
}

int Query(int l, int r) {
    return l == r ? a[l] : Get(0, a.size() - 1, l, r);
}

// int main() {
//     std::ios::sync_with_stdio(0); std::cin.tie(0);

//     int a[8] = { 1, 4, 7, 2, 5, 8, 3, 6 };

//     Init(8, a);

//     std::cout << Query(0, 3) << "\n";
//     std::cout << Query(1, 7) << "\n";
//     std::cout << Query(5, 5) << "\n";
//     std::cout << Query(2, 4) << "\n";
// }

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 3828 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 104 ms 3828 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 104 ms 3824 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 374 ms 8440 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 384 ms 8276 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 369 ms 8276 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 398 ms 8276 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 370 ms 8272 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 369 ms 8368 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 372 ms 8276 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1