oj.uz

Submission #321745

# Submission time Handle Problem Language Result Execution time Memory
321745 2020-11-13T08:51:00 Z lohacho Secret (JOI14_secret) C++14
100 / 100
 519 ms 8428 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)1004;
int val[1004][1004], NN;

void Init(int N, int A[]) {
    NN = N;
    function<void(int, int)> sol = [&](int s, int e){
        if(s == e){
            val[s][e] = A[s];
            return;
        }
        int mid = (s + e) / 2;
        sol(s, mid), sol(mid + 1, e);
        int pos = (s + mid) / 2 + 1;
        for(int i = s; i < mid; ++i){
            while(pos < i){
                pos = (pos + mid) / 2 + 1;
            }
            if(pos > i){
                val[i][mid] = Secret(val[i][pos - 1], val[pos][mid]);
//                cout << i << ' ' << mid << ' ' << val[i][mid] << endl;
            }
        }
        pos = (mid + 1 + e) / 2;
        for(int i = e; i > mid + 1; --i){
            while(pos > i){
                pos = (mid + 1 + pos) / 2;
            }
            if(pos < i){
                val[mid + 1][i] = Secret(val[mid + 1][pos], val[pos + 1][i]);
//                cout << mid + 1 << ' ' << i << ' ' << val[mid + 1][i] << endl;
            }
        }
    };
    sol(0, N - 1);
}

int Query(int L, int R) {
    if(L == R){
        return val[L][R];
    }
    int s = 0, e = NN - 1, mid;
    while(true){
        mid = (s + e) / 2;
        if(L <= mid && R > mid){
            return Secret(val[L][mid], val[mid + 1][R]);
        }
        if(mid < L){
            s = mid + 1;
        }
        else{
            e = mid;
        }
    }
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 4460 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 142 ms 4460 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 147 ms 4460 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 503 ms 8300 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 500 ms 8300 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 513 ms 8428 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 503 ms 8272 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 519 ms 8312 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 519 ms 8300 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 503 ms 8428 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1