#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return 63 - __builtin_clzll(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
// mt19937_64 rng(69);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T& container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
const int LOG_N = 11, N = 1000;
int n;
vector<int> a;
int rmq[LOG_N][N];
// int Secret(int x, int y){return min(x + y, 1e9);}
void dnc(int l, int r, int layer){
if (l == r){
rmq[layer][l] = a[l];
return;
}
int mid = (l + r) >> 1;
rmq[layer][mid] = a[mid];
rmq[layer][mid + 1] = a[mid + 1];
for(int i = mid - 1; i>=l; --i) rmq[layer][i] = Secret(a[i], rmq[layer][i + 1]);
for(int i = mid + 2; i<=r; ++i) rmq[layer][i] = Secret(rmq[layer][i - 1], a[i]);
dnc(l, mid, layer + 1);
dnc(mid + 1, r, layer + 1);
}
void Init(int _n, int A[]) {
n = _n;
for(int i = 0; i<n; ++i) a.push_back(A[i]);
dnc(0, n-1, 0);
}
int Query(int L, int R) {
if (L == R) return a[L];
int l = 0, r = n - 1;
int layer = -1;
while(true){
layer++;
int mid = (l + r) >> 1;
if (L > mid){l = mid + 1; continue;}
if (R <= mid){r = mid; continue;}
return Secret(rmq[layer][L], rmq[layer][R]);
}
}
// int main(void){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
2748 KB |
Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
103 ms |
2736 KB |
Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
102 ms |
2640 KB |
Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
360 ms |
4436 KB |
Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
375 ms |
4268 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
370 ms |
4436 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
364 ms |
4436 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
361 ms |
4452 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
366 ms |
4264 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
365 ms |
4420 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
