제출 #860902

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

prize

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

using namespace std;

#define ll long long
#define pii pair<int, int>

const int MAX = 2e5 + 5, BLOCK = 450;

int tree[MAX];
vector<int> H[MAX];
int det = 1e9;

void update(int pos, int val){
    for(int i = pos; i < MAX; i += (-i & i)){
        tree[i] += val;
    }
}

int q(int l, int r){
    if(l != 1) return q(1, r) - q(1, l - 1);
    int res = 0;
    for(int i = r; i > 0; i -= (-i & i)){
        res += tree[i];
    }
    return res;
}

int find_best(int n){
    for(int i = 0; i < min(BLOCK, n); i++){
        H[i] = ask(i);
        det = max(det, H[i][0] + H[i][1]);
    }
    set<int> s;
    for(int i = 0; i < n; i++){
        s.insert(i);
    }
    while(true){
        int l = 0, r = n - 1;
        while(l < r){
            int mid = (l + r) / 2;
            auto itr = s.lower_bound(mid);
            if(itr != s.begin()){
                if(*itr - mid > mid - *(prev(itr))){
                    mid = *(prev(itr));
                }
                else{
                    mid = *itr;
                }
            }
            else{
                mid = *itr;
            }
            if(H[mid].empty()){
                H[mid] = ask(mid);
            }
            if(H[mid][0] + H[mid][1] == 0) return mid;
            if(H[mid][0] + H[mid][1] != det){
                update(mid + 1, 1);
                s.erase(mid);
                break;
            }
            if(H[mid][1] - q(mid + 2, n)){
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
    } 
}

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