Submission #952298

#	Time	Username	Problem	Language	Result	Execution time	Memory
952298		Em1L	Secret (JOI14_secret)	C++17	100 / 100	398 ms	8440 KiB

secret

#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 / 100