oj.uz

Submission #634041

# Submission time Handle Problem Language Result Execution time Memory
634041 2022-08-23T17:51:23 Z Ronin13 Secret (JOI14_secret) C++14
100 / 100
 513 ms 4976 KB 
#include "secret.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define f first
#define s second
#define pii pair<int,int>
using namespace std;

map<pii, int> mp;
const int NMAX = 10001;
int a[NMAX];
int n;
int xx;
void build(int l, int r){
    int m = (l + r) / 2;
    if(l == r){
        mp[{l, r}] = a[l];
        return;
    }
    build(l, m);
    build(m + 1, r);
    if(l == 0 && r == n - 1) return;
    if((l != xx + 1) || (r != n - 1)){
    for(int i = l; i <= m; i++){
        int x = mp[{i, m}];
        int y = mp[{m + 1, r}];
        mp[{i, r}] = Secret(x, y);
    }
    }
    if(r - l > 1){
    if((l != 0) || (r != xx)){
    for(int i = r; i >= m + 1; i--){
        int x = mp[{l, m}];
        int y = mp[{m + 1, i}];
        mp[{l, i}] = Secret(x, y);
    }}}
}

void Init(int N, int A[]) {
    n = N;
    for(int i = 0; i < n; i++) a[i] = A[i];
    //cout << 1;
    xx = (n - 1) / 2;
    build(0, n - 1);

}

int Query(int L, int R) {
    //cout << n << "\n";
  int l = 0, r = n - 1;
  if(L == R){
    return a[R];
  }
  while(true){
    int m = (l + r) / 2;
    if(R <= m) {
        r = m;
        continue;
    }
    if(L > m){
        l = m + 1;
        continue;
    }
    break;
  }
  int m = (l + r) / 2;
  int x = mp[{L, m}];
  int y = mp[{m + 1, R}];
  return Secret(x, y);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 2692 KB Output is correct - number of calls to Secret by Init = 3576, maximum number of calls to Secret by Query = 1
2 Correct 158 ms 2664 KB Output is correct - number of calls to Secret by Init = 3584, maximum number of calls to Secret by Query = 1
3 Correct 130 ms 2728 KB Output is correct - number of calls to Secret by Init = 3594, maximum number of calls to Secret by Query = 1
4 Correct 485 ms 4896 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
5 Correct 513 ms 4824 KB Output is correct - number of calls to Secret by Init = 7988, maximum number of calls to Secret by Query = 1
6 Correct 472 ms 4932 KB Output is correct - number of calls to Secret by Init = 7988, maximum number of calls to Secret by Query = 1
7 Correct 489 ms 4856 KB Output is correct - number of calls to Secret by Init = 7988, maximum number of calls to Secret by Query = 1
8 Correct 496 ms 4976 KB Output is correct - number of calls to Secret by Init = 7988, maximum number of calls to Secret by Query = 1
9 Correct 494 ms 4824 KB Output is correct - number of calls to Secret by Init = 7988, maximum number of calls to Secret by Query = 1
10 Correct 482 ms 4856 KB Output is correct - number of calls to Secret by Init = 7988, maximum number of calls to Secret by Query = 1