Submission #120772

#	Time	Username	Problem	Language	Result	Execution time	Memory
120772		youngyojun	Meetings (IOI18_meetings)	C++11	60 / 100	3648 ms	786436 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 INF (1000)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<ll, ll> pll;
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 bool debug = 0;
 
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;
	void prt() {
		printf("NOD : s=%d, e=%d, m=%d, l=%d, r=%d\n", s, e, m, l, r);
	}
} nod[MAXN*2]; int nodN;
vector<int> XQV[MAXN];
int nodXI[MAXN];
 
struct CHN {
	deque<pll> CH;
	ll delta;
	int s, e;
 
	void prt() {
		puts("CHN");
		printf("delta = %lld, s = %d, e = %d\n", delta, s, e);
		for(auto &v : CH) printf("(%lld,%lld) ", v.first, v.second);
		puts("");
	}
 
	void cut(ll a, ll b) {
		ll startY = lnef(a, b, s);
		ll endY = lnef(a, b, e);
		if(debug) {
			printf("cut a=%lld, b=%lld, startY=%lld, endY=%lld // %lld %lld\n", a, b, startY, endY, CH[0].second + delta, CH.back().second + delta);
		}
		if(CH[0].second + delta < startY) return;
		if(endY <= CH.back().second + delta) {
			delta = 0;
			CH = deque<pll>();
			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;
		for(; (a-c) * (X+1) <= d-b; X++);
		for(; (a-c) * (X-1) >= d-b; X--);
		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 && X < CH[0].first) CH.ef(X, Y - delta);
		if(s < CH[0].first) CH.ef(s, startY - delta);
	}
 
	void merge(CHN &v) {
		int n = sz(CH), m = sz(v.CH);
		if(m <= n) {
			ll dt = -delta + v.delta;
			for(int i = 0; i < m; i++)
				CH.eb(v.CH[i].first, v.CH[i].second + dt);
			e = v.e;
		} else {
			ll dt = delta - v.delta;
			for(int i = n; i--;)
				v.CH.ef(CH[i].first, CH[i].second + dt);
			v.s = s;
			swap(*this, v);
		}
	}
 
	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];
 
	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(debug) {
			printf("AFTER CUT calTree idx=%d\n", idx);
			v.prt();
			chn.prt();
			chnR.prt();
		}
 
		chn.merge(chnR);
	}
	if(debug) {
		printf("calTree idx=%d\n", idx);
		v.prt();
		chn.prt();
		puts("");
	}
 
	if(nodXI[v.s] == idx) {
		for(int qi : XQV[v.s]) {
			preAns[qi] = chn.get(QE[qi]);
			if(debug) {
				printf("preAns %d ; %lld\n", qi, preAns[qi]);
			}
		}
	}
}
 
ll realAns[MAXQ];
void naive() {
	for(int i = 1; i <= Q; i++) {
		int s = A[i], e = B[i];
		ll t = INFLL;
		for(int j = s; j <= e; j++) {
			ll sum = 0, h = H[j];
			for(int k = j; s <= k; k--) {
				upmax(h, ll(H[k]));
				sum += h;
			}
			h = H[j];
			for(int k = j+1; k <= e; k++) {
				upmax(h, ll(H[k]));
				sum += h;
			}
			upmin(t, sum);
		}
		realAns[i] = t;
	}
}
 
void process() {
	//naive();
 
	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);
 
	if(debug) {
		for(int i = 1; i <= N; i++) printf("%d ", H[i]); puts("");
		for(int i = 1; i <= N; i++) printf("%d ", HO[i]); puts("");
		for(int i = 1; i <= N; i++) printf("%d ", HRO[i]); puts("");
	}
	for(int i = 1; i <= Q; i++) {
		C[i] = HO[mnseg.get(A[i], B[i])];
		QS[i] = C[i];
		QE[i] = B[i];
 
		if(debug) {
			printf("qur %d ; %d %d / %d %d %d\n", i, QS[i], QE[i], A[i], B[i], C[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]];
		if(debug) {
			printf("FIRST ANS %d ; %lld\n", i, Ans[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;
	if(debug) {
		puts("\n\nREVERSE\n\n");
		for(int i = 1; i <= N; i++) printf("%d ", H[i]); puts("");
		for(int i = 1; i <= N; i++) printf("%d ", HO[i]); puts("");
		for(int i = 1; i <= N; i++) printf("%d ", HRO[i]); puts("");
	}
	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;
		if(debug) {
			printf("SECOND ANS %d ; %lld\n", i, t);
		}
	}
 
	return;
	for(int i = 1; i <= Q; i++) {
		if(Ans[i] != realAns[i]) {
			printf("WRONG on %d : %lld but %lld\n", i, realAns[i], Ans[i]);
			exit(-1);
		}
	}
}
 
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;
}

Compilation message (stderr)

meetings.cpp: In function 'void process()':
meetings.cpp:236:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int i = 1; i <= N; i++) printf("%d ", H[i]); puts("");
   ^~~
meetings.cpp:236:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int i = 1; i <= N; i++) printf("%d ", H[i]); puts("");
                                                    ^~~~
meetings.cpp:237:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int i = 1; i <= N; i++) printf("%d ", HO[i]); puts("");
   ^~~
meetings.cpp:237:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int i = 1; i <= N; i++) printf("%d ", HO[i]); puts("");
                                                     ^~~~
meetings.cpp:238:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int i = 1; i <= N; i++) printf("%d ", HRO[i]); puts("");
   ^~~
meetings.cpp:238:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int i = 1; i <= N; i++) printf("%d ", HRO[i]); puts("");
                                                      ^~~~
meetings.cpp:265:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int i = 1; i <= N; i++) printf("%d ", H[i]); puts("");
   ^~~
meetings.cpp:265:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int i = 1; i <= N; i++) printf("%d ", H[i]); puts("");
                                                    ^~~~
meetings.cpp:266:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int i = 1; i <= N; i++) printf("%d ", HO[i]); puts("");
   ^~~
meetings.cpp:266:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int i = 1; i <= N; i++) printf("%d ", HO[i]); puts("");
                                                     ^~~~
meetings.cpp:267:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int i = 1; i <= N; i++) printf("%d ", HRO[i]); puts("");
   ^~~
meetings.cpp:267:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int i = 1; i <= N; i++) printf("%d ", HRO[i]); puts("");
                                                      ^~~~

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