Submission #619206

#	Time	Username	Problem	Language	Result	Execution time	Memory
619206		Sergio_2357	The Big Prize (IOI17_prize)	C++17	20 / 100	3063 ms	2436 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

struct SegTree {
    int n;
    vi v;
    void update(int i, int val)
    {
        int p = i + n;
        v[p] = val;
        while (p /= 2)
            v[p] = v[2 * p] + v[2 * p + 1];
    }
    int query(int i, int l, int h, int ql, int qh)
    {
        if (h <= ql || qh <= l)
            return 0;
        if (l <= ql && qh <= h)
            return v[i];
        int m = (h - l) / 2 + l;
        return query(2 * i, l, m, ql, qh) + query(2 * i + 1, m, h, ql, qh);
    }
    int query(int l, int h)
    {
        return query(1, 0, n, l, h);
    }
    SegTree() { }
    SegTree(int sz)
    {
        n = 1;
        while (n < sz)
            n *= 2;
        v = vi(2 * n + 1, 0);
    }
};

int n;
SegTree st;
set<int> nl;
map<int, vi> qr;
int llc = 0;
int res = -1;

vi ask2(int i)
{
    if (qr.count(i))
        return qr[i];
    qr[i] = ask(i);
    return qr[i];
}

int cask(int i)
{
    while (nl.count(i))
        i++;
    if (i >= n)
        i--;
    while (nl.count(i))
        i--;
    auto p = ask2(i);
    if (p[0] + p[1] == 0)
        res = i;
    if (p[0] + p[1] < llc) {
        nl.insert(i);
        st.update(i, 1);
        return 2;
    }
    int l = p[0] - st.query(0, i);
    int r = p[1] - st.query(i, n);
    return l < r;
}

int find_best(int n_)
{
    n = n_;
    st = SegTree(n);
    for (int i = 0; i < min(n, 500); i++) {
        auto p = ask2(i);
        llc = max(llc, p[0] + p[1]);
        if (p[0] + p[1] == 0)
            return i;
    }
    while (res == -1) {
        int l = 0;
        int h = n;
        while (l < h - 1) {
            int m = (h - l) / 2 + l;
            int r = cask(m);
            if (r == 2)
                break;
            if (!r)
                h = m;
            else
                l = m;
        }
    }
    return res;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80