#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "secret.h"
using namespace std;
using namespace __gnu_pbds;
// Optimization
//#pragma GCC optimize("O3")
#define endl '\n'
// Shortcut
// #define int long long
#define eb emplace_back
#define pb push_back
#define pob pop_back
#define mp make_pair
#define upb upper_bound
#define lwb lower_bound
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define Ford(i, r, l) for (int i = r; i > l; i--)
#define FordE(i, r, l) for (int i = r; i >= l; i--)
#define Fora(i, a) for (auto i : a)
// I/O & Debug
#define PrintV(a) Fora(iiii, a) cout << iiii << ' '; cout << endl;
#define PrintVl(a) Fora(iiii, a) cout << iiii << endl;
#define PrintA(a, l, r) for (int iiii = l; iiii <= r; iiii++) cout << a[iiii] << ' '; cout << endl;
#define PrintAl(a, l, r) for (int iiii = l; iiii <= r; iiii++) cout << a[iiii] << endl;
#define Ptest(x) return cout << x, 0;
#define gl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
/*
#define debug(args...){ string _sDEB = #args; replace(_sDEB.begin(), _sDEB.end(), ',', ' '); stringstream _ssDEB(_sDEB); istream_iterator<string> _itDEB(_ssDEB); DEB(_itDEB, args); }
void DEB(istream_iterator<string> it) {}
template<typename T, typename... Args>
void DEB(istream_iterator<string> it, T a, Args... args){
cout << *it << " = " << a << endl;
DEB(++it, args...);
}
*/
// Functions
//#define isvowel(a) (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
#define bend(a) a.begin(), a.end()
#define rbend(a) a.rbegin(), a.rend()
#define mset(a) memset(a, 0, sizeof(a))
#define mset1(a) memset(a, 1, sizeof(a))
#define msetn1(a) memset(a, -1, sizeof(a))
#define msetinf(a) memset(a, 0x3f, sizeof(a))
#define gcd __gcd
#define __builtin_popcount __builtin_popcountll
//mt19937 rando(chrono::steady_clock::now().time_since_epoch().count());
//int randt(int l, int r){ return (rando() % (r - l + 1) + l); }
// Data Structure
#define pque priority_queue
#define mts multiset
#define y0 _y0_
#define y1 _y1_
#define div divi
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <ld> vld;
typedef vector <string> vs;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <vi > vvi;
typedef vector <vll > vvll;
typedef vector <pii > vpii;
typedef vector <pll > vpll;
const int N = 1e3, PWN = 1024, LV = 11;
int mod = 1e9 + 7, mod1 = 998244353, mod2 = 1e9 + 9, inf = 1e9;
ll infll = 1e18 + 7;
//int Secret(int X, int Y);
int b[N];
int table[LV][PWN];
int maxlev, sz;
map <pair <int, int>, int> mpp;
void build(int lev = 0, int l = 0, int r = sz){
int m = (l + r - 1) >> 1;
table[lev][m] = b[m];
FordE(i, m - 1, l){
if (mpp.find({i, m}) == mpp.end()){
table[lev][i] = Secret(b[i], table[lev][i + 1]);
mpp[{i, m}] = table[lev][i];
}
else{
table[lev][i] = mpp[{i, m}];
}
}
if (m + 1 < r){
table[lev][m + 1] = b[m + 1];
For(i, m + 2, r){
if (mpp.find({m + 1, i}) == mpp.end()){
table[lev][i] = Secret(table[lev][i - 1], b[i]);
mpp[{m + 1, i}] = table[lev][i];
}
else{
table[lev][i] = mpp[{m + 1, i}];
}
}
}
if (l + 1 != r){
build(lev + 1, l, m + 1);
build(lev + 1, m + 1, r);
}
}
void Init(int n, int a[]){
For(i, 0, n){
b[i] = a[i];
}
sz = n;
maxlev = __builtin_clz(n) ^ 31;
if ((1 << maxlev) != n){
sz = 1 << ++maxlev;
}
build();
// For(lev, 0, maxlev){
// For(i, 0, n){
// cout << lev << ' ' << i << ' ' << table[lev][i] << endl;
// }
// }
}
int Query(int l, int r){
if (l == r){
return b[l];
}
int k2 = __builtin_clz(l ^ r) ^ 31;
int lev = maxlev - 1 - k2;
int m = ((r >> k2) << k2) - 1;
// cout << "Q " << l << ' ' << r << ' ' << k2 << ' ' << lev << endl;
int ans = table[lev][l];
if (r > m){
ans = Secret(ans, table[lev][r]);
}
return ans;
}
// DEBUGGING SECTION ======================================================================================================
//int n, q;
//int a[N];
//
//int Secret(int X, int Y){
// return (X + 2 * (Y / 2) < inf) ? (X + 2 * (Y / 2)) : inf;
//}
//
//signed main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// cin >> n;
// For(i, 0, n){
// cin >> a[i];
// }
// Init(n, a);
// cin >> q;
// while (q--){
// int l, r; cin >> l >> r; cout << Query(l, r) << endl;
// }
//}
/*
==================================+
INPUT: |
------------------------------ |
8
1 4 7 2 5 8 3 6
4
0 3
1 7
5 5
2 4
------------------------------ |
==================================+
OUTPUT: |
------------------------------ |
------------------------------ |
==================================+
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
2680 KB |
Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
146 ms |
2768 KB |
Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
150 ms |
2936 KB |
Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
512 ms |
4856 KB |
Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
513 ms |
4856 KB |
Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
505 ms |
4984 KB |
Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
519 ms |
4936 KB |
Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
526 ms |
4856 KB |
Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
520 ms |
4832 KB |
Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
525 ms |
5052 KB |
Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1 |
