oj.uz

Submission #87840

# Submission time Handle Problem Language Result Execution time Memory
87840 2018-12-02T19:48:45 Z tincamatei Secret (JOI14_secret) C++14
0 / 100
 667 ms 5704 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(l, mid, i, j);
    else
      return Query(mid + 1, r, i, j);
  }
}

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

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 2936 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 37949731.
2 Incorrect 162 ms 3020 KB Wrong Answer: Query(102, 157) - expected : 32612619, actual : 626661664.
3 Incorrect 162 ms 3020 KB Wrong Answer: Query(334, 369) - expected : 363022362, actual : 487993636.
4 Incorrect 587 ms 5480 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 305381472.
5 Incorrect 591 ms 5580 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 468353360.
6 Incorrect 592 ms 5608 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 538068777.
7 Correct 602 ms 5608 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 601 ms 5704 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 667 ms 5704 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 606 ms 5704 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1