#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e3 + 5;
vector<int> v;
namespace RMQ {
int atr[nmax];
int rmq[12][nmax];
void color(int l, int r, int bit = 1) {
//cerr << l << ' ' << r << ' ' << bit << '\n';
if(l + 1 >= r) {
while(l <= r)
atr[l] = bit, l++;
return;
}
int mid = l + r >> 1;
atr[mid] = -bit;
atr[mid + 1] = bit;
color(l, mid - 1, bit + 1);
color(mid + 2, r, bit + 1);
rmq[bit][mid] = v[mid];
rmq[bit][mid + 1] = v[mid + 1];
for(int i = mid - 1; i >= l; i--)
rmq[bit][i] = Secret(v[i], rmq[bit][i + 1]);
for(int i = mid + 2; i <= r; i++)
rmq[bit][i] = Secret(rmq[bit][i - 1], v[i]);
return;
}
namespace IRMQ {
pair<int,int> irmq[12][nmax];
int lg[nmax];
void init(int n, int *vec) {
lg[1] = 0;
for(int i = 2; i <= n; i++)
lg[i] = lg[i >> 1] + 1;
for(int i = 0; i < n; i++)
irmq[0][i] = {abs(vec[i]), vec[i] / abs(vec[i]) * i};
for(int bit = 1; bit < 12; bit++) {
for(int i = 0; i + (1 << bit) <= n; i++)
irmq[bit][i] = min(irmq[bit - 1][i], irmq[bit - 1][i + (1 << bit - 1)]);
}
}
pair<int,int> query(int l, int r) {
int st = lg[r - l + 1];
return min(irmq[st][l], irmq[st][r - (1 << st) + 1]);
}
}
int query(int l, int r) {
if(l == r)
return v[l];
else if(l == r - 1)
return Secret(v[l], v[r]);
auto level = IRMQ::query(l, r);
if(r == -level.second)
return rmq[level.first][l];
if(l == level.second)
return rmq[level.first][r];
return Secret(rmq[level.first][l], rmq[level.first][r]);
}
}
void Init(int N, int A[]) {
v.resize(N);
for(int i = 0; i < N; i++)
v[i] = A[i];
RMQ::color(0, N - 1);
RMQ::IRMQ::init(N, RMQ::atr);
}
int Query(int L, int R) {
return RMQ::query(L, R);
}
Compilation message
secret.cpp: In function 'void RMQ::color(int, int, int)':
secret.cpp:18:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | int mid = l + r >> 1;
| ~~^~~
secret.cpp: In function 'void RMQ::IRMQ::init(int, int*)':
secret.cpp:42:76: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
42 | irmq[bit][i] = min(irmq[bit - 1][i], irmq[bit - 1][i + (1 << bit - 1)]);
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
2428 KB |
Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
121 ms |
2444 KB |
Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
142 ms |
2380 KB |
Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
446 ms |
4384 KB |
Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
461 ms |
4300 KB |
Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
425 ms |
4360 KB |
Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
456 ms |
4336 KB |
Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
469 ms |
4316 KB |
Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
436 ms |
4304 KB |
Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
453 ms |
4328 KB |
Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1 |
