oj.uz

Submission #964239

# Submission time Handle Problem Language Result Execution time Memory
964239 2024-04-16T13:20:12 Z 12345678 Secret (JOI14_secret) C++17
100 / 100
 391 ms 4968 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;

int a[nx], dp[nx], n;
map<pair<int, int>, int> mp;

void solve(int l, int r)
{
    if (l>=r) return;
    int md=(l+r)/2;
    dp[md]=a[md];
    for (int i=md-1; i>=l; i--) mp[{i, md}]=dp[i]=Secret(a[i], dp[i+1]);
    dp[md+1]=a[md+1];
    for (int i=md+2; i<=r; i++) mp[{md+1, i}]=dp[i]=Secret(dp[i-1], a[i]);
    solve(l, md-1);
    solve(md+2, r);
}

int query(int l, int r, int ql, int qr)
{
    if (l==r) return a[l];
    //cout<<"debug "<<l<<' '<<r<<' '<<ql<<' '<<qr<<'\n';
    int md=(l+r)/2;
    if (qr>=md&&ql<=md+1)
    {
        if (ql>md) return mp[{md+1, qr}];
        else if (qr<md+1) return mp[{ql, md}];
        else return Secret(mp[{ql, md}], mp[{md+1, qr}]);
    }
    if (qr<md) return query(l, md-1, ql, qr);
    else return query(md+2, r, ql, qr);
}

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

int Query(int L, int R) {
    return query(0, n-1, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 2904 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 114 ms 3036 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 108 ms 2804 KB Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1
4 Correct 382 ms 4864 KB Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1
5 Correct 391 ms 4948 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
6 Correct 381 ms 4860 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
7 Correct 383 ms 4968 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 384 ms 4848 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 384 ms 4904 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 381 ms 4852 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1