Submission #87841

#	Time	Username	Problem	Language	Result	Execution time	Memory
87841		tincamatei	Secret (JOI14_secret)	C++14	100 / 100	620 ms	5648 KiB

secret

#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 / 100