oj.uz

Submission #321743

# Submission time Handle Problem Language Result Execution time Memory
321743 2020-11-13T08:47:27 Z lohacho Secret (JOI14_secret) C++14
0 / 100
 518 ms 8460 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 - 1;
        }
    }
  return 0;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 142 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 4588 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Incorrect 132 ms 4460 KB Wrong Answer: Query(67, 224) - expected : 202440844, actual : 536870912.
4 Incorrect 495 ms 8396 KB Wrong Answer: Query(384, 458) - expected : 896057572, actual : 536870912.
5 Incorrect 492 ms 8428 KB Wrong Answer: Query(263, 292) - expected : 653448456, actual : 536870912.
6 Incorrect 501 ms 8428 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 536870912.
7 Correct 502 ms 8416 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 500 ms 8460 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 518 ms 8448 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 497 ms 8428 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1