Submission #853022

#	Time	Username	Problem	Language	Result	Execution time	Memory
853022		waldi	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	490 ms	79544 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define inf 1000000000000000000ll
#define infmale 2000000000ll
using namespace std;
typedef long long ll;

struct przedzialowiec{
	int n;
	vector<vector<ll>> liscie;
	vector<ll> mini;
	przedzialowiec(int nn){
		for(n = 1; n < nn;) n <<= 1;
		liscie.resize(n<<1);
		mini.resize(n<<1, inf);
	}
	void wrzuc(int poz, ll wart){
		liscie[poz+n-1].emplace_back(wart);
	}
	void zbuduj(){
		FOR(i, n, n+n-1){
			sort(liscie[i].begin(), liscie[i].end(), greater<ll>());
			if(liscie[i].size()) mini[i] = liscie[i].back();
		}
		for(int i = n; --i;) mini[i] = min(mini[i<<1], mini[i<<1|1]);
	}
	ll mini_prz(int p, int k, int tp, int tk, int w){
		if(p <= tp && tk <= k) return mini[w];
		int sr = (tp+tk)>>1;
		ll ret = inf;
		if(p <= sr) ret = min(ret, mini_prz(p, k, tp, sr, w<<1));
		if(sr < k) ret = min(ret, mini_prz(p, k, sr+1, tk, w<<1|1));
		return ret;
	}
	ll mini_prz(int p, int k){
		return mini_prz(p, k, 1, n, 1);
	}
	void usun(int poz){
		poz += n-1;
		liscie[poz].pop_back();
		mini[poz] = liscie[poz].size() ? liscie[poz].back() : inf;
		while(poz >>= 1) mini[poz] = min(mini[poz<<1], mini[poz<<1|1]);
	}
};

ll plan_roller_coaster(vector<int> s, vector<int> t) {
	int n = s.size();
	
	if(n <= 16){
		vector<vector<ll>> dp(1<<n, vector<ll>(n, inf));
		FOR(maska, 1, (1<<n)-1) REP(ost, n) if(maska>>ost&1){
			if(__builtin_popcount(maska) == 1) dp[maska][ost] = 0ll;
			REP(i, n) if(!(maska>>i&1)) dp[maska+(1<<i)][i] = min(dp[maska+(1<<i)][i], dp[maska][ost] + max(0, t[ost]-s[i]));
		}
		ll wyn = inf;
		REP(i, n) wyn = min(wyn, dp[(1<<n)-1][i]);
		return wyn;
	}
	
	set<int> secik;
	for(int x : s) secik.emplace(x);
	for(int x : t) secik.emplace(x);
	unordered_map<int, int> mapa;
	int it = 0;
	for(int x : secik) mapa[x] = ++it;
	for(int &x : s) x = mapa[x];
	for(int &x : t) x = mapa[x];
	
	int ost = 1;
	przedzialowiec prz(it);
	REP(i, n) prz.wrzuc(s[i], infmale*ll(t[i])+ll(s[i]));
	prz.zbuduj();
	REP(xd, n){
		ll mini = prz.mini_prz(ost, it);
		if(mini == inf) return 1ll;
		ost = mini/infmale;
		prz.usun(mini%infmale);
		// i = gosc o minimalnym t[i] sposrod gosci o s[i]>=ost
		// nie istnieje? return 1ll;
		// ost = t[i]
		// wywal goscia i
	}
	return 0ll;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36