Submission #1138220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138220		anmattroi	The Big Prize (IOI17_prize)	C++17	100 / 100	15 ms	5612 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;

int N;
int st[4*maxn];
constexpr int B = 474;

inline constexpr int csk(const int &u) {return u/B;}
inline constexpr int csd(const int &u) {return u*B;}
inline constexpr int csc(const int &u) {return min(N, (u+1)*B);}

void upd(int u, int d, int r = 1, int lo = 0, int hi = N-1) {
    if (lo == hi) {
        st[r] = d;
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) upd(u, d, r<<1, lo, mid);
    else upd(u, d, r<<1|1, mid+1, hi);
    st[r] = st[r<<1] + st[r<<1|1];
}

int get(int u, int v, int r = 1, int lo = 0, int hi = N-1) {
    if (u > hi || v < lo) return 0;
    if (u <= lo && hi <= v) return st[r];
    int mid = (lo + hi) >> 1;
    return get(u, v, r<<1, lo, mid) + get(u, v, r<<1|1, mid+1, hi);
}

int it[4*maxn];

void build(int r = 1, int lo = 0, int hi = N-1) {
    it[r] = hi-lo+1;
    if (lo == hi) return;
    int mid = (lo + hi) >> 1;
    build(r<<1, lo, mid);
    build(r<<1|1, mid+1, hi);
}

void update(int u, int d, int r = 1, int lo = 0, int hi = N-1) {
    if (lo == hi) {
        it[r] = d;
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) update(u, d, r<<1, lo, mid);
    else update(u, d, r<<1|1, mid+1, hi);
    it[r] = it[r<<1] + it[r<<1|1];
}

int bfind(int k, int r = 1, int lo = 0, int hi = N-1) {
    if (lo == hi) return lo;
    int mid = (lo + hi) >> 1, trai = it[r<<1];
    if (trai >= k) return bfind(k, r<<1, lo, mid);
    return bfind(k-trai, r<<1|1, mid+1, hi);
}

int get_sum(int u, int v, int r = 1, int lo = 0, int hi = N-1) {
    if (u > hi || v < lo) return 0;
    if (u <= lo && hi <= v) return it[r];
    int mid = (lo + hi) >> 1;
    return get_sum(u, v, r<<1, lo, mid) + get_sum(u, v, r<<1|1, mid+1, hi);
}


int find_best(int n) {
    N = n;
    for (int i = 1; i <= 4*N; i++) st[i] = 0;
    build();
    int num = 0;
    vector<int> nho;
    for (int i = 0; i < min(474, N); i++) {
        vector<int> res = ask(i);
        int Prz = (res[0]+res[1]);
        if ((Prz+1LL*Prz*Prz+1) > N) {
            nho.emplace_back(Prz);
            break;
        }
        if (res[0] + res[1] == 0) return i;
        nho.emplace_back(res[0]+res[1]);
    }
    int p = max_element(nho.begin(), nho.end()) - nho.begin();
    for (int i = 0; i < p; i++) {
        upd(i, 1);
        update(i, 0);
    }
    vector<int> Old = ask(p);

    function<int(int)> Fixed = [&](int z) {
        return max(z, p+1);
    };

    for (int o = csk(p); o <= csk(n-1); o++) {
        int P = csc(o)-1, Need = 0;
        while (P >= Fixed(csd(o))) {
            vector<int> Tn = ask(P);
            if (Tn[0] + Tn[1] == 0) return P;
            if (Tn[0] + Tn[1] != nho[p]) {
                update(P, 0);
                upd(P, 1);
                --P;
                continue;
            }
            Need = Old[1] - Tn[1] - get(p, P);
            break;
        }
        if (P < Fixed(csd(o))) continue;
        while (Need--) {
            int lo = get_sum(p, Fixed(csd(o))-1)+1, hi = get_sum(p, csc(o)-1);
            while (hi != lo) {
                int mid = (lo + hi) >> 1,
                    pos = bfind(mid);
                vector<int> res = ask(pos);
                if (res[0] + res[1] == 0) return pos;
                if (res[0] + res[1] != nho[p]) {
                    update(pos, 0);
                    upd(pos, 1);
                    break;
                }
                int How_many = Old[1] - res[1] - get(p, pos);
                if (How_many) hi = mid-1;
                else lo = mid+1;
            }
            if (lo != hi) continue;
            int pos = bfind(lo);
            vector<int> H = ask(pos);
            if (H[0] + H[1] == 0) return pos;
            update(pos, 0);
            upd(pos, 1);
        }
    }

    return 0;
}
//10000 queries
//
//5 different gifts

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