oj.uz

Submission #77728

# Submission time Handle Problem Language Result Execution time Memory
77728 2018-09-30T05:49:45 Z nxteru Secret (JOI14_secret) C++14
100 / 100
 638 ms 9404 KB 
#include <iostream>
#include <vector>
#include "secret.h"
using namespace std;
int n,a[1005][1005];
void bt(int l,int r){
    int m=(l+r)/2;
    for(int i=m-1;i>=l;i--){
        a[i][m]=Secret(a[i][i],a[i+1][m]);
    }
    for(int i=m+2;i<=r;i++){
        a[m+1][i]=Secret(a[m+1][i-1],a[i][i]);
    }
    if(l+3<=m)bt(l,m);
    if(m+4<=r)bt(m+1,r);
}
void Init(int N,int *A){
    n=N;
    for(int i=0;i<n;i++)a[i][i]=A[i];
    bt(0,n-1);
}
int ans(int L,int R,int l,int r){
    int m=(l+r)/2;
    if(R<m)return ans(L,R,l,m);
    if(m+1<L)return ans(L,R,m+1,r);
    if(R==m||L==m+1)return a[L][R];
    return Secret(a[L][m],a[m+1][R]);
}
int Query(int l,int r){
    return ans(l,r,0,n-1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 4540 KB Output is correct - number of calls to Secret by Init = 3577, maximum number of calls to Secret by Query = 1
2 Correct 180 ms 4588 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 182 ms 5004 KB Output is correct - number of calls to Secret by Init = 3594, maximum number of calls to Secret by Query = 1
4 Correct 622 ms 8820 KB Output is correct - number of calls to Secret by Init = 7944, maximum number of calls to Secret by Query = 1
5 Correct 625 ms 8904 KB Output is correct - number of calls to Secret by Init = 7954, maximum number of calls to Secret by Query = 1
6 Correct 597 ms 8968 KB Output is correct - number of calls to Secret by Init = 7954, maximum number of calls to Secret by Query = 1
7 Correct 607 ms 9048 KB Output is correct - number of calls to Secret by Init = 7954, maximum number of calls to Secret by Query = 1
8 Correct 638 ms 9248 KB Output is correct - number of calls to Secret by Init = 7954, maximum number of calls to Secret by Query = 1
9 Correct 634 ms 9404 KB Output is correct - number of calls to Secret by Init = 7954, maximum number of calls to Secret by Query = 1
10 Correct 624 ms 9404 KB Output is correct - number of calls to Secret by Init = 7954, maximum number of calls to Secret by Query = 1