제출 #1138198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138198		anmattroi	커다란 상품 (IOI17_prize)	C++17	0 / 100	25 ms	4040 KiB

prize

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

int N;
int st[2*maxn];

void upd(int u, int d) {
    for (st[u+=N+1] = d; u >>= 1;) st[u] = st[u<<1] + st[u<<1|1];
}

int get(int l, int r) {
    int res = 0;
    for (l += N+1, r += N+2; l < r; l >>= 1, r >>= 1) {
        if (l&1) res += st[l++];
        if (r&1) res += st[--r];
    }
    return res;
}

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 find_best(int n) {
    N = n;
    for (int i = 1; i <= 2*N; i++) st[i] = 0;
    build();
    vector<int> nho;
    for (int i = 0; i < min(500, N); i++) {
        vector<int> res = ask(i);
        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);
    }
    int Need = nho[p] - p;
    int Number = N-nho[p];

    vector<int> Old = ask(p);

    int lo = 0, hi = Number;
    while (Need--) {
        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;
        }
    }
    return 0;
}
//10000 queries
//
//5 different gifts
/*
8
3 2 3 1 3 3 2 3
*/

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