제출 #964239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964239		12345678	Secret (JOI14_secret)	C++17	100 / 100	391 ms	4968 KiB

secret

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