oj.uz

Submission #87839

# Submission time Handle Problem Language Result Execution time Memory
87839 2018-12-02T19:45:00 Z tincamatei Secret (JOI14_secret) C++14
0 / 100
 618 ms 6308 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;

int rez = 0;

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)]) {
      ++rez;
      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, r)]) {
      ++rez;
      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 158 ms 2808 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 37949731.
2 Incorrect 159 ms 3020 KB Wrong Answer: Query(102, 157) - expected : 32612619, actual : 626661664.
3 Incorrect 159 ms 3176 KB Wrong Answer: Query(334, 369) - expected : 363022362, actual : 487993636.
4 Incorrect 594 ms 5696 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 305381472.
5 Incorrect 593 ms 5812 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 468353360.
6 Incorrect 590 ms 5916 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 538068777.
7 Correct 604 ms 6116 KB Output is correct - number of calls to Secret by Init = 5002, maximum number of calls to Secret by Query = 1
8 Correct 603 ms 6116 KB Output is correct - number of calls to Secret by Init = 5002, maximum number of calls to Secret by Query = 1
9 Correct 604 ms 6116 KB Output is correct - number of calls to Secret by Init = 5002, maximum number of calls to Secret by Query = 1
10 Correct 618 ms 6308 KB Output is correct - number of calls to Secret by Init = 5002, maximum number of calls to Secret by Query = 1