oj.uz

Submission #673698

# Submission time Handle Problem Language Result Execution time Memory
673698 2022-12-21T17:44:06 Z whitewind664 Secret (JOI14_secret) C++17
100 / 100
 573 ms 4792 KB 
#include <bits/stdc++.h>
// #include <atcoder/string>
// #include <atcoder/lazysegtree>

using namespace std;


using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;
// using mint = atcoder::modint998244353;
int INF = numeric_limits<int>::max() >> 1;
ll INFL = numeric_limits<ll>::max() >> 1;
ll mod = 998244353;

map<pll, ll> mp;
vector<int> v;
int total = 0;

int Secret(int X, int Y);

void askingInit(int l, int r, int A[])
{
    if (r - l <= 1)
    {
        return;
    }
    int mid = (l + r) / 2;
    ll prevVal = A[mid];
    for (int i = mid - 1; i >= l; i--)
    {
        prevVal = Secret(A[i], prevVal);
        mp[{i,mid}] = prevVal;
    }
    prevVal = A[mid + 1];
    for (int i = mid + 2; i <= r; i++)
    {
        prevVal = Secret(prevVal, A[i]);
        mp[{mid+1,i}] = prevVal;
    }

    askingInit(l, mid, A);
    askingInit(mid + 1, r, A);
}

void Init(int N, int A[])
{
    askingInit(0, N - 1, A);
    v.resize(N);
    for (int i = 0; i < N; i++)
    {
        v[i] = A[i];
    }
    // cout << total << endl;
}

int get(int L, int R)
{
    if (L == R)
    {
        return v[L];
    }
    if (mp.find({L, R}) == mp.end())
    {
        return -1;
    }
    return mp[{L, R}];
}

int Query(int L, int R)
{
    int val1, val2;
    if ((val1 = get(L, R)) != -1)
    {
        return val1;
    }
    for (int i = L; i < R; i++)
    {
        if ((val1 = get(L, i)) != -1 && (val2 = get(i + 1, R)) != -1)
        {
            return Secret(val1, val2);
        }
    }
    return -1;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 2632 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 160 ms 2628 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 181 ms 2652 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 489 ms 4708 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 489 ms 4688 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 449 ms 4740 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 560 ms 4792 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 573 ms 4684 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 541 ms 4688 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 555 ms 4776 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1