# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
643664 | pls33 | Secret (JOI14_secret) | C++17 | 471 ms | 4872 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
#pragma endregion
map<p32, int> queries;
vvi32 dst;
int leading_bit(int i)
{
return 31 - __builtin_clz(i);
}
int secret_wrapper(int l, int r);
void Init(int n, int a[])
{
dst = vvi32(leading_bit(n) + 1, vi32(n));
for (size_t row = 0; row < dst.size(); row++)
{
int length = (1 << row);
for (int center = length; center < n + length; center += 2 * length)
{
int val = 0;
for (int i = center; i < center + length && i <= n; i++)
{
dst[row][i] = val;
if (i != n)
{
val = secret_wrapper(a[i], val);
}
}
for (int i = min(n - 1, center - 1); i >= center - length; i--)
{
dst[row][i] = secret_wrapper(a[i], dst[row][i + 1]);
}
}
}
}
int Query(int l, int r)
{
r++;
int row = leading_bit(l ^ r);
return secret_wrapper(dst[row][l], dst[row][r]);
}
int secret_wrapper(int l, int r)
{
auto it = queries.find({l, r});
int val = 0;
if (it != queries.end())
{
val = it->second;
}
else
{
val = Secret(l, r);
queries[{l, r}] = val;
}
return val;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |