oj.uz

Submission #25344

# Submission time Handle Problem Language Result Execution time Memory
25344 2017-06-21T08:08:30 Z kajebiii Secret (JOI14_secret) C++14
100 / 100
 633 ms 19292 KB 
#include "secret.h"
#include <vector>
#include <stdio.h>

using namespace std;

const int MAX_N = 1e3 + 100;
const int ROOT_N = 32;

int Nr[MAX_N], W[MAX_N][MAX_N], Cnt;
int L[MAX_N][MAX_N], R[MAX_N][MAX_N];

void makeLR(int a, int b) {
    if(a == b) return;
    int m = (a+b) >> 1;
    Cnt++;
    for(int i=a; i<=m; i++) for(int j=m+1; j<=b; j++)
        W[i][j] = Cnt;
    L[Cnt][m] = Nr[m];
    R[Cnt][m+1] = Nr[m+1];
    for(int i=m-1; i>=a; i--) L[Cnt][i] = Secret(Nr[i], L[Cnt][i+1]);
    for(int i=m+2; i<=b; i++) R[Cnt][i] = Secret(R[Cnt][i-1], Nr[i]);
    makeLR(a, m);
    makeLR(m+1, b);
}
int getQ(int a, int b) {
    if(a == b) return Nr[a];
    int w = W[a][b];
    return Secret(L[w][a], R[w][b]);
}
void Init(int N, int A[]) {
    for(int i=0; i<N; i++) Nr[i] = A[i];
    makeLR(0, N-1);
}

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 19292 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 163 ms 19292 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 163 ms 19292 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 633 ms 19292 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 609 ms 19292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 633 ms 19292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 593 ms 19292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 619 ms 19292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 626 ms 19292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 626 ms 19292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1