#include <bits/stdc++.h>
using namespace std;
int Secret(int l, int r);
map<pair<int,int>,int>dp;
map<pair<int,int>,bool>calculed;
template<class T, T m_(T, T)> struct SegmentTree{
int n; vector<T> ST;
SegmentTree(){}
SegmentTree(vector<T> &a){
n = a.size(); ST.resize(n << 1);
for (int i=n;i<(n<<1);i++)ST[i]=a[i-n];
for (int i=n-1;i>0;i--)ST[i]=m_(ST[i<<1],ST[i<<1|1]);
}
void update(int pos, T val){ // replace with val
ST[pos += n] = val;
for (pos >>= 1; pos > 0; pos >>= 1)
ST[pos] = m_(ST[pos<<1], ST[pos<<1|1]);
}
T query(int l, int r){ // [l, r]
T ansL, ansR; bool hasL = 0, hasR = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
ansL=(hasL?m_(ansL,ST[l++]):ST[l++]),hasL=1;
if (r & 1)
ansR=(hasR?m_(ST[--r],ansR):ST[--r]),hasR=1;
}
if (!hasL) return ansR; if (!hasR) return ansL;
return m_(ansL, ansR);
}
}; // Give vector of leaves and merge function
int merge(int a,int b){
if(calculed[{a,b}]){
return dp[{a,b}];
}
dp[{a,b}]=Secret(a,b);
calculed[{a,b}]=true;
return dp[{a,b}];
}
vector<int>AA;
SegmentTree<int,merge>st(AA);
void Init(int n, int a[]){
vector<int>arr(n);
for(int i=0;i<n;i++){
arr[i]=a[i];
}
SegmentTree<int,merge>stt(arr);
st=stt;
}
int Query(int l,int r){
return st.query(l,r);
}
Compilation message
secret.cpp: In member function 'T SegmentTree<T, m_>::query(int, int)':
secret.cpp:27:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
27 | if (!hasL) return ansR; if (!hasR) return ansL;
| ^~
secret.cpp:27:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
27 | if (!hasL) return ansR; if (!hasR) return ansL;
| ^~
secret.cpp: In function 'int Query(int, int)':
secret.cpp:51:24: warning: 'ansR' may be used uninitialized in this function [-Wmaybe-uninitialized]
51 | return st.query(l,r);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
125 ms |
4356 KB |
Output is partially correct - number of calls to Secret by Init = 510, maximum number of calls to Secret by Query = 10 |
| 2 |
Partially correct |
134 ms |
4176 KB |
Output is partially correct - number of calls to Secret by Init = 511, maximum number of calls to Secret by Query = 12 |
| 3 |
Partially correct |
122 ms |
4436 KB |
Output is partially correct - number of calls to Secret by Init = 512, maximum number of calls to Secret by Query = 11 |
| 4 |
Partially correct |
383 ms |
6416 KB |
Output is partially correct - number of calls to Secret by Init = 998, maximum number of calls to Secret by Query = 13 |
| 5 |
Partially correct |
395 ms |
6484 KB |
Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 13 |
| 6 |
Partially correct |
369 ms |
5552 KB |
Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 4 |
| 7 |
Partially correct |
406 ms |
5812 KB |
Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 13 |
| 8 |
Partially correct |
385 ms |
5848 KB |
Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 14 |
| 9 |
Partially correct |
395 ms |
5872 KB |
Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 12 |
| 10 |
Partially correct |
390 ms |
6164 KB |
Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 14 |
