oj.uz

Submission #354231

# Submission time Handle Problem Language Result Execution time Memory
354231 2021-01-21T15:12:20 Z parsabahrami Secret (JOI14_secret) C++17
100 / 100
 522 ms 4588 KB 
#include "secret.h"
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 1e3 + 10;
int M[N], B[11][N], A[N], n;

void divide(int l = 0, int r = n, int h = 0) {
    if (r - l < 2) {
        B[h][l] = A[l];
        return;
    }
    int mid = (l + r) >> 1;
    B[h][mid] = A[mid], B[h][mid - 1] = A[mid - 1];
    for (int i = mid - 2; i >= l; i--) B[h][i] = Secret(A[i], B[h][i + 1]);
    for (int i = mid + 1; i < r; i++) B[h][i] = Secret(B[h][i - 1], A[i]);
    for (int i = mid; i < r; i++) M[i] |= 1 << h;
    divide(l, mid, h + 1), divide(mid, r, h + 1);
}

void Init(int _n, int a[]) {
    n = _n;
    for (int i = 0; i < n; i++) A[i] = a[i];
    divide();
}

int Query(int L, int R) {
    if (L == R) return A[L];
    else {
        int c = __builtin_ctz(M[L] ^ M[R]);
        return Secret(B[c][L], B[c][R]);
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 2412 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 142 ms 2412 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 142 ms 2412 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 507 ms 4460 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 505 ms 4588 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 510 ms 4332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 503 ms 4332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 508 ms 4588 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 522 ms 4516 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 513 ms 4332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1