oj.uz

Submission #87841

# Submission time Handle Problem Language Result Execution time Memory
87841 2018-12-02T20:06:19 Z tincamatei Secret (JOI14_secret) C++14
100 / 100
 620 ms 5648 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;

vector<int> vect;
map<pair<int, int>, bool> exista;
map<pair<int, int>, int>  val;

void aintdfs(int l, int r) {
  int mid = (l + r) / 2;
  for(int i = mid; i >= l; --i) {
    if(!exista[make_pair(i, mid)]) {
      exista[make_pair(i, mid)] = true;
      val[make_pair(i, mid)] = Secret(vect[i], val[make_pair(i + 1, mid)]);
    }
  }

  for(int i = mid + 1; i <= r; ++i) {
    if(!exista[make_pair(mid + 1, i)]) {
      exista[make_pair(mid + 1, i)] = true;
      val[make_pair(mid + 1, i)] = Secret(val[make_pair(mid + 1, i - 1)], vect[i]);
    }
  }
  if(l < r) {
    aintdfs(l, mid);
    aintdfs(mid + 1, r);
  }
}

void Init(int n, int V[]) {
  vect.assign(V, V + n);
  for(int i = 0; i < n; ++i) {
    exista[make_pair(i, i)] = true;
    val[make_pair(i, i)] = V[i];
  }

  aintdfs(0, n - 1);
}

int Query(int i, int j, int l, int r) {
  if(l == r)
    return vect[l];
  else {
    int mid = (l + r) / 2;
    if(i <= mid && j > mid)
      return Secret(val[make_pair(i, mid)], val[make_pair(mid + 1, j)]);
    else if(j <= mid)
      return Query(i, j, l, mid);
    else
      return Query(i, j, mid + 1, r);
  }
}

int Query(int l, int r) {
  return Query(l, r, 0, vect.size() - 1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 2876 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 174 ms 2932 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 176 ms 3000 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 601 ms 5556 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 607 ms 5636 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 606 ms 5636 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 608 ms 5636 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 611 ms 5648 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 620 ms 5648 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 614 ms 5648 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1