# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1019684 | codefox | Secret (JOI14_secret) | C++14 | 594 ms | 524288 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;
vector<vector<int>> rright;
vector<vector<int>> lleft;
/*
int secret(int a, int b)
{
cout << a << " " << b << endl;
int x;
cin >> x;
return x;
}
*/
void initialize(int l, int r, int A[])
{
if (l==r) return;
if (l==r+1) return;
int m = (l+r)/2;
for (int i = m+1; i < r; i++)
{
rright[m].push_back(Secret(rright[m].back(), A[i]));
}
for (int i = m-2; i >= l; i--)
{
lleft[m-1].push_back(Secret(lleft[m-1].back(), A[i]));
}
initialize(l, m-2, A);
initialize(m+1, r, A);
}
void Init(int N, int A[]) {
rright.assign(N, vector<int>());
lleft.assign(N, vector<int>());
for (int i = 0; i < N; i++)
{
rright[i].push_back(i);
lleft[i].push_back(i);
}
initialize(0, N, A);
}
int Query(int L, int R) {
int ss = R-L+1;
if (rright[L].size()>=ss)
{
return rright[L][ss-1];
}
if (lleft[R].size()>=ss)
{
return lleft[R][ss-1];
}
for (int i = L+1; i <= R; i++)
{
if (rright[i].size()>= R-i+1 && lleft[i-1].size()>= i-L)
{
return Secret(rright[i][R-i], lleft[i-1][i-1-L]);
}
}
return 0;
}
/*
int main()
{
int n, q;
cin >> n;
int A[n];
for (int i = 0; i < n; i++)
{
cin >> A[i];
}
cin >> q;
Init(n, A);
for (int i = 0; i < q; i++)
{
int a, b;
cin >> a >> b;
cout << Query(a, b) << "\n";
}
}
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |