Submission #557813

#	Time	Username	Problem	Language	Result	Execution time	Memory
557813		Kaipalo	Secret (JOI14_secret)	C++14	100 / 100	502 ms	8360 KiB

secret

#include "secret.h"
#include <iostream>

using namespace std;

int n;
int cal[1005][1005];

void build(int l, int r, int A[]) {
    int mid = (l + r) / 2;
    cal[mid][mid] = A[mid];
    cal[mid+1][mid+1] = A[mid+1];
    for (int i = mid-1; i >= l; i--) cal[i][mid] = Secret(A[i], cal[i+1][mid]);
    for (int i = mid+2; i <= r; i++) cal[mid+1][i] = Secret(cal[mid+1][i-1], A[i]);

    if (l < mid) build(l, mid, A);
    if (mid+1 < r) build(mid+1, r, A);
}

int query(int wantL, int wantR, int l = 0, int r = n-1) {
    int mid = (l + r) / 2;
    if (l == r) return cal[l][r];
    if (wantL <= mid && wantR > mid)
        return Secret( cal[wantL][mid], cal[mid+1][wantR] );

    if (wantL > mid) return query(wantL, wantR, mid+1, r);
    else return query(wantL, wantR, l, mid);
}


void Init(int N, int A[]) {
    n = N;
    build(0, n-1, A);
}

int Query(int L, int R) {
    return query(L, R);
}

/*
8
1 4 7 2 5 8 3 6
4
0 3
1 7
5 5
2 4
ans:
13
32
8
13
*/

• Subtask 1: 100 / 100