제출 #292819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292819		amoo_safar	커다란 상품 (IOI17_prize)	C++17	100 / 100	60 ms	2936 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;


const int N = 2e5 + 10;

pii A[N];
pii Ask(int i){
	if(A[i] != pii(-1, -1)) return A[i];

	vector<int> res = ask(i - 1);
	pii tmp = {res[0], res[1]};
	return A[i] = tmp;
}

int mx;
vector<int> V;

int fen[N];
void Add(int idx, int d){
	//if(d == -1) cerr << "--- " << idx << '\n';
	for(; idx < N; idx += idx & -idx)
		fen[idx] += d;
}
int Get(int idx){
	int res = 0;
	for(; idx; idx -= idx & -idx)
		res += fen[idx];
	return res;
}
int Get0(int L, int R){
	if(R < L) return 0;
	return (R - L + 1) - (Get(R) - Get(L - 1));
}

int Bin(int x){
	int res = 0, res2;
	for(int lg = 18; lg >= 0; lg--){
		res2 = res | (1 << lg);
		if(res2 >= N) continue;
		if(fen[res2] < x){
			x -= fen[res2];
			res = res2;
		}
	}
	return res + 1;
}
struct fun {
	int L, R, bl, br, rq;
	fun (int _L, int _R, int _bl, int _br, int _rq){
		L = _L;
		R = _R;
		bl = _bl;
		br = _br;
		rq = _rq;
	}
};
vector< fun > slv;

int find_best(int n) {
	fill(A, A + n, pii(-1, -1));
	memset(fen, 0, sizeof fen);
	mx = -1; V.clear();
	
	for(int i = 1; i <= n; i++) Add(i, 1);

	pii fst = Ask(n / 2);
	mx = fst.F + fst.S;
	V = {};

	slv.pb( fun(1, n, 0, 0, mx) );

	int L, R;
	while(!slv.empty()){
		fun la = slv.back();
		slv.pop_back();
		//cerr << "! " << la.L << ' ' << la.R << " : " << la.rq << '\n';
		if(la.rq == 0) continue;

		L = la.L;
		R = la.R;

		int sm = Get(R) - Get(L - 1);
		assert(sm >= la.rq);

		int mid = Bin(Get(L - 1) + ((sm + 1) / 2));
		//cerr << "# " << mid << '\n';
		pii tmp = Ask(mid);
		//
		if(tmp.F + tmp.S > mx){
			mx = tmp.F + tmp.S;
			for(auto x : V) Add(x, -1);
			V.clear();
			slv.clear();
			slv.pb(fun(1, n, 0, 0, mx - Get0(1, n)));
			continue;
		}
		if(tmp.F + tmp.S == mx){
			int c0 = Get0(L, mid - 1);
			//cerr << "c0 : " << c0 << '\n';
			slv.pb(fun(L, mid - 1, la.bl, tmp.S, tmp.F - la.bl - c0));
			slv.pb(fun(mid + 1, R, tmp.F, la.br, la.rq - (tmp.F - la.bl - c0)));
			//slv.pb({{L, mid - 1}, });
			//slv.pb({{mid + 1, R}, });
			V.pb(mid);
			continue;
		}
		Add(mid, -1);
		//slv.pb(la);
		slv.pb(fun(L, R, la.bl, la.br, la.rq - 1));
	}

	for(int i = 1; i <= n; i++)
		if(A[i] == pii(0, 0))
			return i - 1;
	assert(false);
	return 0;
}

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