oj.uz

답안 #778586

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
778586 2023-07-10T12:51:24 Z benjaminkleyn 커다란 상품 (IOI17_prize) C++17
0 / 100
 75 ms 720 KB 
#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[i]) 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 = min(n - 1, 500); j >= 4; j--)
    {
        Ask(j);
        if (L[j] + R[j] == 0)
            return j;
        if (L[j] == j)
        {
            i = j;
            break;
        }
    }
    v = i;

    while (i < n - 1)
    {
        i = max_idx[mp(L[i], R[i])];
        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));
                if (L[i + (1 << j)] + R[i + (1 << j)] == 0)
                    return i + (1 << j);
                i = max_idx[mp(L[i], R[i])];
            }
        while (i < n - 1)
        {
            Ask(++i);
            if (L[i] + R[i] == 0) return i;
            if (L[i] + R[i] == L[v] + R[v]) break;
        }
    }
    for (int j = 0; j < n && j < 500; j++)
    {
        Ask(j);
        if (L[j] + R[j] == 0)
            return j;
    }
    return 0;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 720 KB Output is correct
2 Correct 3 ms 696 KB Output is correct
3 Correct 3 ms 696 KB Output is correct
4 Correct 5 ms 552 KB Output is correct
5 Correct 3 ms 688 KB Output is correct
6 Incorrect 75 ms 608 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 692 KB Output is correct
2 Correct 4 ms 696 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 2 ms 688 KB Output is correct
6 Incorrect 34 ms 648 KB Incorrect
7 Halted 0 ms 0 KB -