oj.uz

Submission #412732

# Submission time Handle Problem Language Result Execution time Memory
412732 2021-05-27T11:57:11 Z jhnah917 Secret (JOI14_secret) C++14
100 / 100
 552 ms 8516 KB 
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#ifndef LOCAL
#include "secret.h"
#endif
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL // avoid compile error
int Secret(int a, int b){ return 0; }
#endif

int N, A[1010], B[1010][1010];

void Seg_Init(int s, int e){
    if(s == e) return;
    int m = s + e >> 1;
    B[m][m] = A[m];
    for(int i=m-1; i>=s; i--) B[i][m] = Secret(A[i], B[i+1][m]);
    B[m+1][m+1] = A[m+1];
    for(int i=m+2; i<=e; i++) B[m+1][i] = Secret(B[m+1][i-1], A[i]);
    Seg_Init(s, m);
    Seg_Init(m+1, e);
}

void Init(int n, int a[]){
    N = n;
    for(int i=1; i<=N; i++) A[i] = a[i-1];
    for(int i=1; i<=N; i++) B[i][i] = A[i];
    Seg_Init(1, N);
}

int Seg_Query(int s, int e, int l, int r){
    int m = s + e >> 1;
    if(l <= m && m < r) return Secret(B[l][m], B[m+1][r]);
    if(r <= m) return Seg_Query(s, m, l, r);
    else return Seg_Query(m+1, e, l, r);
}

int Query(int l, int r){
    l++; r++;
    if(l == r) return A[l];
    return Seg_Query(1, N, l, r);
}

Compilation message

secret.cpp: In function 'void Seg_Init(int, int)':
secret.cpp:20:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |     int m = s + e >> 1;
      |             ~~^~~
secret.cpp: In function 'int Seg_Query(int, int, int, int)':
secret.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int m = s + e >> 1;
      |             ~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 4380 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 150 ms 4420 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 176 ms 4548 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 526 ms 8196 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 527 ms 8296 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 538 ms 8412 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 542 ms 8280 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 538 ms 8380 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 534 ms 8260 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 552 ms 8516 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1