/*input
*/
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
int Nas;
vii pref(1000, vi(1000));
vii suff(1000, vi(1000));
vb did(1000, false);
vi sk;
void make(int l, int r) {
int m = (l + r) / 2;
if (did[m]) return;
did[m] = true;
if (r - l <= 1) return;
suff[m][m] = sk[m];
if (l <= m - 1)
suff[m - 1][m] = Secret(sk[m - 1], sk[m]);
for (int i = m - 2; l <= i; i--)
suff[i][m] = Secret(sk[i], suff[i + 1][m]);
pref[m + 1][m + 1] = sk[m + 1];
if (m + 2 <= r)
pref[m + 1][m + 2] = Secret(sk[m + 1], sk[m + 2]);
for (int i = m + 3; i <= r; ++i)
pref[m + 1][i] = Secret(pref[m + 1][i - 1], sk[i]);
make(l, m);
make(m + 1, r);
}
void Init(int N, int A[]) {
Nas = N;
sk.resize(N);
for (int i = 0; i < N; ++i)
sk[i] = A[i];
make(0, N - 1);
}
int Query(int L, int R) {
if (L == R) return sk[L];
if (L + 1 == R) return Secret(sk[L], sk[R]);
int l = 0, r = Nas - 1;
// printf("L = %d, R = %d\n", L, R);
while (l < r) {
// printf("l = %d, r = %d\n", l, r);
int m = (l + r) / 2;
if (L <= m and m + 1 <= R) {
return Secret(suff[L][m], pref[m + 1][R]);
}
else if (m < L) l = m + 1;
else r = m;
}
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
162 ms |
10360 KB |
Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
157 ms |
10360 KB |
Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
158 ms |
10360 KB |
Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
532 ms |
12244 KB |
Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
530 ms |
12280 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
540 ms |
12152 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
530 ms |
12280 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
544 ms |
12464 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
536 ms |
12280 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
541 ms |
12184 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
