oj.uz

Submission #236659

# Submission time Handle Problem Language Result Execution time Memory
236659 2020-06-02T18:17:19 Z DS007 Secret (JOI14_secret) C++14
100 / 100
 510 ms 9464 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
 
const int N_ = 1000;
int val[N_][N_];
bool done[N_][N_];
 
int n, *a;
 
void pre(int l, int r) {
    if (l == r)
        return;
 
    int mid = (l + r) / 2;
    for (int i = mid - 1, temp = a[mid]; i >= l; i--) {
        if (done[i][mid]) {
            temp = val[i][mid];
            continue;
        }
 
        temp = Secret(a[i], temp);
        val[i][mid] = temp;
        done[i][mid] = true;
    }
 
    for (int i = mid + 2, temp = a[mid + 1]; i <= r; i++) {
        if (done[mid + 1][i]) {
            temp = val[mid + 1][i];
            continue;
        }
 
        temp = Secret(temp, a[i]);
        val[mid + 1][i] = temp;
        done[mid + 1][i] = true;
    }
 
    pre(l, mid);
    pre(mid + 1, r);
}
 
void Init(int N, int A[]) {
    n = N;
    a = A;
 
    for (int i = 0; i < n; i++)
        val[i][i] = a[i], done[i][i] = true;
 
    pre(0, n - 1);
}
 
int query_util(int l, int r, int tl, int tr) {
    int mid = (l + r) / 2;
    if (tl <= mid && mid < tr)
        return Secret(val[tl][mid], val[mid + 1][tr]);
    else if (tr <= mid)
        return query_util(l, mid, tl, tr);
    else
        return query_util(mid + 1, r, tl, tr);
}
 
int Query(int L, int R) {
    if (done[L][R])
        return val[L][R];
    return query_util(0, n - 1, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 4984 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 149 ms 4984 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 149 ms 4984 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 504 ms 9260 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 507 ms 9464 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 503 ms 9336 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 510 ms 9208 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 505 ms 9336 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 508 ms 9304 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 509 ms 9456 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1