oj.uz

Submission #708536

# Submission time Handle Problem Language Result Execution time Memory
708536 2023-03-12T03:07:33 Z joelgun14 Secret (JOI14_secret) C++17
100 / 100
 539 ms 4608 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
// create a disjoint sparse table like structure
// use nodes, recursive cari jawaban kind of
// ada fungsi query
struct node {
  node *l, *r;
  int le, re, mi;
  vector<int> a;
};
vector<int> arr;
struct disjoint_sparse_table {
  int size = 0;
  node *head = new node();
  void build(node *nd, int l, int r) {
    nd->le = l, nd->re = r, nd->mi = (l + r) >> 1;  
    if(l == r) {
      nd->a.push_back(arr[l]);
      return;
    }
    nd->l = new node(), nd->r = new node();
    int mid = (l + r) >> 1;
    build(nd->l, l, mid), build(nd->r, mid + 1, r);
    for(int i = l; i <= mid; ++i)
      nd->a.push_back(get(nd->l, i, mid));
    for(int i = mid + 1; i <= r; ++i)
      nd->a.push_back(get(nd->r, mid + 1, i));
    //cout << "L R " << l << " " << r << endl;
    //for(auto i : nd->a)
    //  cout << i << " ";
    //cout << endl;
  }
  int get(node *nd, int l, int r) {
    int cl = nd->le, cr = nd->re, mi = nd->mi;
    //cout << "GET " << l << " " << r << " " << cl << " " << cr << endl;
    if(cl == cr)
      return nd->a[0];
    if(l <= mi && r > mi) {
      // has to be in between
      return Secret(nd->a[l - cl], nd->a[r - cl]);
    }
    else {
      if(r <= mi)
        return get(nd->l, l, r);
      else
        return get(nd->r, l, r);
    }
  }
};
disjoint_sparse_table dst;
void Init(int N, int A[]) {
  for(int i = 0; i < N; ++i)
    arr.push_back(A[i]);
  dst.build(dst.head, 0, N - 1);
}

int Query(int L, int R) {
  return dst.get(dst.head, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 2464 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 146 ms 2580 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 132 ms 2532 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 456 ms 4532 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 455 ms 4584 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 458 ms 4608 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 478 ms 4468 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 506 ms 4576 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 487 ms 4512 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 539 ms 4608 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1