# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
76523 |
2018-09-14T12:09:04 Z |
Noam527 |
Secret (JOI14_secret) |
C++14 |
|
655 ms |
6096 KB |
#include "secret.h"
#include <bits/stdc++.h>
#define endl '\n'
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll hs = 199, inf = 1e18;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;
/*
int Secret(int X, int Y) {
cout << "? " << X << " " << Y << endl;
int rtn;
cin >> rtn;
return rtn;
}
*/
map<pair<int, int>, int> ANS;
bool calced(int l, int r) {
return ANS.count({ l, r });
}
int n;
vector<int> a;
int S(int l, int r) {
if (l == r) return a[l];
if (calced(l, r)) return ANS[{l, r}];
if (calced(l, r - 1)) return ANS[{l, r}] = Secret(ANS[{l, r - 1}], a[r]);
return ANS[{l, r}] = Secret(a[l], ANS[{l + 1, r}]);
}
void preprocess(int l, int r) {
if (l == r) return;
int mid = (l + r) / 2;
for (int i = mid + 1; i <= r; i++)
S(mid + 1, i);
for (int i = mid; i >= l; i--)
S(i, mid);
preprocess(l, mid);
preprocess(mid + 1, r);
}
void Init(int N, int A[]) {
n = N;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = A[i];
for (int i = 0; i < n; i++)
ANS[{i, i}] = a[i];
preprocess(0, n - 1);
}
int query(int l, int r, int ql, int qr) {
int mid = (l + r) / 2;
if (qr <= mid) return query(l, mid, ql, qr);
if (mid + 1 <= ql) return query(mid + 1, r, ql, qr);
return Secret(S(ql, mid), S(mid + 1, qr));
}
int Query(int L, int R) {
if (L == R) return a[L];
return query(0, n - 1, L, R);
}
/*
int main() {
int nn;
cin >> nn;
int *A = new int[nn];
for (int i = 0; i < nn; i++) cin >> A[i];
Init(nn, A);
while (1) {
cout << "your query: ";
int l, r;
cin >> l >> r;
cout << "my answer: " << Query(l, r) << endl;
}
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
2684 KB |
Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1 |
2 |
Correct |
178 ms |
2852 KB |
Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1 |
3 |
Correct |
178 ms |
3048 KB |
Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1 |
4 |
Correct |
613 ms |
5220 KB |
Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1 |
5 |
Correct |
603 ms |
5480 KB |
Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1 |
6 |
Correct |
609 ms |
5676 KB |
Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1 |
7 |
Correct |
638 ms |
5944 KB |
Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1 |
8 |
Correct |
637 ms |
5944 KB |
Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1 |
9 |
Correct |
625 ms |
6096 KB |
Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1 |
10 |
Correct |
655 ms |
6096 KB |
Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1 |