Submission #743486

#	Time	Username	Problem	Language	Result	Execution time	Memory
743486		Valters07	Secret (JOI14_secret)	C++14	100 / 100	444 ms	8884 KiB

secret

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