Submission #1155841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155841		onbert	The Big Prize (IOI17_prize)	C++17	100 / 100	15 ms	5348 KiB

prize

#include <bits/stdc++.h>
using namespace std;

std::vector<int> ask(int i);
const int maxn = 2e5 + 5, INF = 1e9;
int N;
vector<int> ans[maxn];
bool start = false;
int mx = 0;
set<int> s;
map<int,int> MX, MN;
set<int> good;
int mxcnt = 0;

vector<int> qry(int i) {
    if (ans[i].size() != 2) ans[i] = ask(i);
    if (start){
        if (ans[i][0] + ans[i][1] == mx) {
            if (!s.count(ans[i][0])) {
                s.insert(ans[i][0]);
                MX[ans[i][0]] = MN[ans[i][0]] = i;
            } else {
                MX[ans[i][0]] = max(i, MX[ans[i][0]]);
                MN[ans[i][0]] = min(i, MN[ans[i][0]]);
            }
        } else {
            good.insert(i);
        }
    }
    return ans[i];
}

void reset() {
    while (s.size()) s.erase(*s.begin());
    while (good.size()) good.erase(*good.begin());
    MX.clear(); MN.clear();
    mxcnt = 0;
    s.insert(INF);
    good.insert(INF);
    for (int i=0;i<N;i++) if (ans[i].size() == 2) {
        if (ans[i][0] + ans[i][1] == mx) {
            if (!s.count(ans[i][0])) {
                s.insert(ans[i][0]);
                MX[ans[i][0]] = MN[ans[i][0]] = i;
            } else {
                MX[ans[i][0]] = max(i, MX[ans[i][0]]);
                MN[ans[i][0]] = min(i, MN[ans[i][0]]);
            }
        } else {
            good.insert(i);
        }
    }
}

int find_best(int n) {
    N = n;
    // if (n <= 5000) {
    //     for (int i=0;i<n;i++) {
    //         if (qry(i)[0] + qry(i)[1] == 0) return i;
    //     }
    // }
    start = true;
    s.insert(INF);
    good.insert(INF);
    for (int i=0;i<n;i++) {
        vector<int> vec = qry(i);
        if (vec[0]+ vec[1] == 0) return i;
        if (vec[0] + vec[1] > mx) {mx = vec[0] + vec[1]; reset();}
        if (vec[0] + vec[1] == mx) {
            int l = i, r = min(i + 1023, n-1);
            if (i+1023 < n) {
                if (qry(i+1023) == vec) r = n-1;
                else if (qry(i+1023)[0] + qry(i+1023)[1] > mx) {
                    mx = qry(i+1023)[0] + qry(i+1023)[1];
                    reset();
                }
            }
            if (s.count(vec[0])) l = MX[vec[0]];
            if (*s.upper_bound(vec[0]) != INF) r = MN[*s.upper_bound(vec[0])] - 1;
            r = min(r, *good.upper_bound(l) - 1);
            while (l < r) {
                int mid = (l+r+1)/2;
                if (qry(mid) == vec) l = mid;
                else r = mid-1;
                if (qry(mid)[0] + qry(mid)[1] > mx) {
                    mx = qry(mid)[0] + qry(mid)[1];
                    reset();
                    l--;
                    break;
                }
            }
            i = l;
            mxcnt += l - i + 1;
        }
    }
	return 0;
}

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