oj.uz

Submission #743486

# Submission time Handle Problem Language Result Execution time Memory
743486 2023-05-17T12:19:53 Z Valters07 Secret (JOI14_secret) C++14
100 / 100
 444 ms 8884 KB 
#include "secret.h"
#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define en cin.close();return 0;
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N = 1e3+5;
vector<int> a;
int val[N][N], n0;
map<pair<int,int>,int> mp;
int ask(int v1, int v2)
{
    pair<int,int> t = {v1,v2};
    if(mp.count(t))
        return mp[t];
    mp[t]=Secret(v1,v2);
    return mp[t];
}
void askinterval(int l, int r)
{
    if(l<r)
    {
        int cur = a[l];
        for(int i = l+1;i<=r;i++)
            cur=ask(cur,a[i]),
            val[l][i]=cur;
    }
    else
    {
        swap(l,r);
        int cur = a[r];
        for(int i = r-1;i>=l;i--)
            cur=ask(a[i],cur),
            val[i][r]=cur;
    }
}
void go(int l, int r)
{
    if(r-l+1<=2)
        return;
    int mid = (l+r)/2;
    askinterval(mid,l);
    askinterval(mid+1,r);
    go(l,mid);
    go(mid+1,r);
}
void Init(int n, int tmpa[])
{
    n0=n;
    a.resize(n);
    for(int i = 0;i<n;i++)
        a[i]=tmpa[i],
        val[i][i]=a[i];
    go(0,n-1);
}
int getval(int lb, int rb, int l = 0, int r = n0-1)
{
    int mid = (l+r)/2;
    if(lb<=mid&&mid+1<=rb)
        return Secret(val[lb][mid],val[mid+1][rb]);
    if(rb<=mid)
        return getval(lb,rb,l,mid);
    return getval(lb,rb,mid+1,r);
}
int Query(int l, int r)
{
    if(l==r)
        return val[l][r];
    return getval(l,r);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 4772 KB Output is correct - number of calls to Secret by Init = 3324, maximum number of calls to Secret by Query = 1
2 Correct 122 ms 4660 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 124 ms 4612 KB Output is correct - number of calls to Secret by Init = 3341, maximum number of calls to Secret by Query = 1
4 Correct 441 ms 8884 KB Output is correct - number of calls to Secret by Init = 7483, maximum number of calls to Secret by Query = 1
5 Correct 438 ms 8768 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
6 Correct 440 ms 8844 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
7 Correct 433 ms 8712 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
8 Correct 427 ms 8656 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
9 Correct 435 ms 8652 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
10 Correct 444 ms 8716 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1