Submission #120764

#	Time	Username	Problem	Language	Result	Execution time	Memory
120764		youngyojun	Meetings (IOI18_meetings)	C++11	60 / 100	1827 ms	381364 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define ef emplace_front
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
const ld EPS = 1e-8;
ll operator * (const pll &a, const pll &b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll &a, const pll &b, const pll &c) { return a*b + b*c + c*a; }
ll lnef(ll a, ll b, ll x) { return a*x + b; }

const int MAXN = 750055;
const int MAXQ = 750055;
const int MX = 1048576;

struct MNSEG {
	int d[MX*2];

	void init(int dt[], int n) {
		for(int i = 0; i < n; i++)
			d[i+MX] = dt[i];
		fill(d+MX+n, d+MX*2, INF);
		for(int i = MX; --i;)
			d[i] = min(d[i<<1], d[i<<1|1]);
	}

	int get(int s, int e) {
		int r = INF; for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
			if(s&1) { upmin(r, d[s]); s++; }
			if(~e&1) { upmin(r, d[e]); e--; }
		}
		return r;
	}
} mnseg;

struct NOD {
	int s, e, m, l, r;
} nod[MAXN*2]; int nodN;
vector<int> XQV[MAXN];
int nodXI[MAXN];

pil arr[MAXN*8];
struct DEQ {
	int s, e, __s;

	void set(int __s) { s = e = __s*2; this->__s = __s; }
	bool empty() { return s == e; }
	pil& front() { return arr[s]; }
	pil& back() { return arr[e-1]; }
	pil& operator [] (const unsigned int a) { return arr[s+a]; }
	void pop_front() { s++; }
	void pop_back() { e--; }
	void emplace_back(const int &a, const ll &b) { arr[e++] = pil(a, b); }
	void emplace_back(const pil& p) { arr[e++] = p; }
	void emplace_front(const int &a, const ll &b) { arr[--s] = pil(a, b); }
	void emplace_front(const pil& p) { arr[--s] = p; }
	void clear() { set(__s); }
	unsigned int size() { return e-s; }
};

struct CHN {
	DEQ CH;
	ll delta;
	int s, e;

	void set(int __s, int __e) { CH.set(__s+MAXN); }
	void cut(ll a, ll b) {
		ll startY = lnef(a, b, s);
		ll endY = lnef(a, b, e);
		if(CH[0].second + delta < startY) return;
		if(endY <= CH.back().second + delta) {
			delta = 0;
			CH.clear();
			CH.eb(s, startY);
			if(s != e) CH.eb(e, endY);
			return;
		}

		int t = 0, n = sz(CH);
		for(; t+1 < n && lnef(a, b, CH[t+1].first) <= CH[t+1].second + delta; t++);

		ll c = (CH[t+1].second - CH[t].second) / (CH[t+1].first - CH[t].first);
		ll d = CH[t].second + delta - c * CH[t].first;
		int X = ld(d-b) / (a-c) + EPS;
		ll Y = lnef(a, b, X);

		for(int i = 0; i <= t; i++) CH.pop_front();
		if(Y < lnef(c, d, X) && X+1 < CH[0].first) CH.ef(X+1, lnef(c, d, X+1) - delta);
		if(s < X) CH.ef(X, Y - delta);
		CH.ef(s, startY - delta);
	}

	void mergeback(CHN &v) {
		ll dt = -delta + v.delta;
		for(int i = 0, n = sz(v.CH); i < n; i++)
			CH.eb(v.CH[i].first, v.CH[i].second + dt);
		e = v.e;
	}
	void mergefront(CHN &v) {
		ll dt = -delta + v.delta;
		for(int i = sz(v.CH); i--;)
			CH.ef(v.CH[i].first, v.CH[i].second + dt);
		s = v.s;
	}

	ll get(int X) {
		if(s == e) return CH[0].second + delta;
		int ls = 0, le = sz(CH)-2; for(int m; ls < le;) {
			m = (ls + le + 1) >> 1;
			if(CH[m].first <= X && X <= CH[m+1].first) {
				ls = m;
				break;
			}
			if(X < CH[m].first) le = m-1;
			else ls = m;
		}

		ll a = (CH[ls+1].second - CH[ls].second) / (CH[ls+1].first - CH[ls].first);
		ll b = CH[ls].second + delta - a * CH[ls].first;
		return lnef(a, b, X);
	}
};

int H[MAXN], HO[MAXN], HRO[MAXN];
int A[MAXQ], B[MAXQ], C[MAXQ];
int QS[MAXQ], QE[MAXQ];
ll Ans[MAXQ], preAns[MAXQ];

int N, Q;

int makeTree(int s, int e) {
	nodN++; int idx = nodN;
	if(!nodXI[s]) nodXI[s] = idx;
	nod[idx].s = s;
	nod[idx].e = e;
	if(s == e) return idx;
	nod[idx].m = HO[mnseg.get(s+1, e)];
	nod[idx].l = makeTree(s, nod[idx].m-1);
	nod[idx].r = makeTree(nod[idx].m, e);
	return idx;
}

void makeTree() {
	nodN = 0;
	fill(nodXI, nodXI+MAXN, 0);
	for(int i = 0; i < MAXN; i++) XQV[i].clear();
	for(int i = 1; i <= Q; i++) XQV[QS[i]].eb(i);
	makeTree(0, N);
}

void calTree(CHN &chn, int idx) {
	auto &v = nod[idx];
	chn.set(v.s, v.e);

	if(v.s == v.e) {
		chn.CH.eb(v.s, H[v.s]);
		chn.delta = 0;
		chn.s = v.s;
		chn.e = v.e;
	} else {
		CHN chnR;
		calTree(chn, v.l);
		calTree(chnR, v.r);
		chnR.delta += H[v.s] + ll(v.m - v.s - 1) * H[v.m];
		chnR.cut(H[v.m], chn.CH.back().second + chn.delta + ll(-v.m + 1) * H[v.m]);

		if(sz(chn.CH) < sz(chnR.CH)) {
			chnR.mergefront(chn);
			swap(chn, chnR);
		} else chn.mergeback(chnR);

		chnR.CH.clear();
	}

	if(nodXI[v.s] == idx) {
		for(int qi : XQV[v.s]) {
			preAns[qi] = chn.get(QE[qi]);
		}
	}
}

void process() {
	H[0] = INF;
	iota(HO+1, HO+N+1, 1);
	sort(HO+1, HO+N+1, [&](int a, int b) {
		if(H[a] != H[b]) return H[a] > H[b];
		return a < b;
	});
	for(int i = 0; i <= N; i++) HRO[HO[i]] = i;
	mnseg.init(HRO, N+1);

	for(int i = 1; i <= Q; i++) {
		C[i] = HO[mnseg.get(A[i], B[i])];
		QS[i] = C[i];
		QE[i] = B[i];
	}
	
	makeTree();
	{ CHN chn; calTree(chn, 1); }

	for(int i = 1; i <= Q; i++) {
		Ans[i] = preAns[i] + ll(C[i] - A[i]) * H[C[i]];
	}
	
	reverse(H+1, H+N+1);
	for(int i = 1; i <= N; i++) HO[i] = N+1 - HO[i];
	for(int i = 1; i <= N; i++) HRO[HO[i]] = i;
	mnseg.init(HRO, N+1);
	for(int i = 1; i <= Q; i++) {
		A[i] = N+1 - A[i];
		B[i] = N+1 - B[i];
		swap(A[i], B[i]);
		C[i] = N+1 - C[i];
		QS[i] = C[i];
		QE[i] = B[i];
	}

	makeTree();
	{ CHN chn; calTree(chn, 1); }

	for(int i = 1; i <= Q; i++) {
		ll t = preAns[i] + ll(C[i] - A[i]) * H[C[i]];
		if(t < Ans[i]) Ans[i] = t;
	}
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
		std::vector<int> R) {
	::N = sz(H);
	::Q = sz(L);

    for(int i = 1; i <= Q; i++) {
    	::A[i] = L[i-1] + 1;
    	::B[i] = R[i-1] + 1;
	}
	for(int i = 1; i <= N; i++) {
		::H[i] = H[i-1];
	}

	process();

	vector<ll> V;
	for(int i = 1; i <= Q; i++) V.eb(Ans[i]);
	return V;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 40