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 "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
bool asked[200000];
int L[200000], R[200000];
map<pair<int, int>, int> max_idx;
int v, N;
int t[800000] = {0};
void update(int v, int tl, int tr, int idx, int val)
{
if (tl == tr)
{
t[v] = max(t[v], val);
return;
}
int tm = (tl + tr) / 2;
if (idx <= tm)
update(2 * v, tl, tm, idx, val);
else
update(2 * v + 1, tm + 1, tr, idx, val);
t[v] = max(t[2 * v], t[2 * v + 1]);
}
int query(int v, int tl, int tr, int l, int r)
{
if (r < tl || tr < l) return 0;
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) / 2;
return max(
query(2 * v, tl, tm, l, r),
query(2 * v + 1, tm + 1, tr, l, r)
);
}
void Ask(int i)
{
if (asked[200000]) return;
asked[i] = true;
vector<int> res = ask(i);
L[i] = res[0], R[i] = res[1];
if (max_idx.find(mp(L[i], R[i])) == max_idx.end())
max_idx[mp(L[i], R[i])] = i;
else
max_idx[mp(L[i], R[i])] = max(max_idx[mp(L[i], R[i])], i);
if (L[i] + R[i] == L[v] + R[v])
update(1, 0, N - 1, i, L[i]);
}
int find_best(int n)
{
memset(asked, false, sizeof(asked));
max_idx = map<pair<int,int>,int>();
N = n;
int i = 0;
Ask(i);
for (int j = 0; j < n && j < 500; j++)
{
Ask(j);
if (L[j] + R[j] == 0)
return j;
if (L[j] + R[j] > L[i] + R[i])
i = j;
}
v = i;
while (i < n)
{
for (int j = 18; j >= 0; j--)
if (i + (1 << j) < n)
{
if (query(1, 0, n - 1, i, i + (1 << j)) > L[i])
continue;
Ask(i + (1 << j));
i = max_idx[mp(L[i], R[i])];
}
while (i < n)
{
Ask(++i);
if (L[i] + R[i] == 0) return i;
if (L[i] + R[i] == L[v] + R[v]) break;
}
}
return n - 1;
}
Compilation message (stderr)
prize.cpp: In function 'void Ask(int)':
prize.cpp:39:21: warning: array subscript 200000 is above array bounds of 'bool [200000]' [-Warray-bounds]
39 | if (asked[200000]) return;
| ~~~~~~~~~~~~^
prize.cpp:6:6: note: while referencing 'asked'
6 | bool asked[200000];
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |