Submission #1135863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135863		Thanhs	Secret (JOI14_secret)	C++20	0 / 100	379 ms	11888 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
using namespace std;

#define name "TENBAI"
#define fi first
#define se second
// #define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))

mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 1e3 + 5;

map<pair<int, int>, int> mp;
int n, a[NM], sum = 0;
pair<int, int> b[NM][NM];

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

void dnc(int l, int r)
{
    if (l >= r)
        return;
    int m = l + r >> 1;
    for (int i = m - 1; i >= l; i--)
        mp[{i, m}] = Secret(a[i], mp[{i + 1, m}]);
    for (int i = m + 2; i <= r; i++)
        mp[{m + 1, i}] = Secret(mp[{m + 1, i - 1}], a[i]);
    for (int i = l; i <= m; i++)
        for (int j = m + 1; j <= r; j++)
            b[i][j] = {mp[{i, m}], mp[{m + 1, j}]};
    dnc(l, m); 
    dnc(m + 1, r);
}

void Init(int N, int A[])
{
    n = N;
    for (int i = 1; i <= n; i++)
    {
        a[i] = A[i - 1];
        mp[{i, i}] = a[i];
    }
    dnc(1, n);
}

int Query(int l, int r)
{
    l++; r++;
    if (l == r)
        return a[l];
    return Query(b[l][r].fi, b[l][r].se);
}

// signed main()
// {
//     Init(2, );
//     cout << Query(0, 1);
// }

• Subtask 1: 0 / 100