제출 #162021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
162021		Alexa2001	Secret (JOI14_secret)	C++17	100 / 100	628 ms	8444 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1005;

int n;
int res[Nmax][Nmax], A[Nmax];

void divide(int st, int dr)
{
    if(dr - st <= 3)
    {
        if(res[st+1][dr-1] == -1)
            res[st+1][dr-1] = Secret(A[st+1], A[dr-1]);
        return;
    }

    int mid = (st + dr) / 2;

    divide(st, mid);
    divide(mid+1, dr);

    int i;
    for(i=mid-1; i>=st; --i)
        if(res[i][mid] == -1)
            res[i][mid] = Secret(A[i], res[i+1][mid]);

    for(i=mid+2; i<=dr; ++i)
        if(res[mid+1][i] == -1)
            res[mid+1][i] = Secret(res[mid+1][i-1], A[i]);
}

void Init(int N, int _A[])
{
    n = N;

    int i, j;
    for(i=0; i<n; ++i) A[i] = _A[i];

    for(i=0; i<n; ++i)
        for(j=i; j<n; ++j)
            res[i][j] = -1;

    for(i=0; i<n; ++i) res[i][i] = A[i];

    divide(0, n-1);
}

int answer(int st, int dr, int L, int R)
{
    if(dr - st <= 3)
    {
        if(res[L][R] != -1) return res[L][R];/// lungime 4

        /// lungime 3
        assert(R - L == 2);
        if(res[L][L+1] != -1) return Secret(res[L][L+1], A[R]);
            else
            {
                assert(res[R-1][R] != -1);
                return Secret(A[L], res[R-1][R]);
            }
    }

    int mid = (st + dr) / 2;

    if(L <= mid && mid + 1 <= R)
        return Secret(res[L][mid], res[mid+1][R]);

    if(R <= mid) return answer(st, mid, L, R);
        else return answer(mid+1, dr, L, R);
}

int Query(int L, int R)
{
    if(L == R) return A[L];
    if(L + 1 == R) return Secret(A[L], A[R]);

    /// lungime minim 3
    return answer(0, n-1, L, R);
}

• Subtask 1: 100 / 100