Submission #1105544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105544		Lib_Steal	Meetings (IOI18_meetings)	C++17	60 / 100	4003 ms	786432 KiB

meetings

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int> 
#define sz(a) ((int) (a).size())
#define QAQ
using namespace std;
const int N = 7.5e5 + 7, M = 1 << 24;
const ll inf = 1e18;
struct RMQ {
	int a[N], mx[20][N], lg[N];
	void init (int n) {
		L(i, 2, n) lg[i] = lg[i >> 1] + 1;
		L(i, 1, n) mx[0][i] = i;
		L(i, 1, 19)
			L(j, 1, n - (1 << i) + 1) 
				mx[i][j] = a[mx[i - 1][j]] > a[mx[i - 1][j + (1 << (i - 1))]] ? 
					mx[i - 1][j] : mx[i - 1][j + (1 << (i - 1))];
	}
	inline int queryp (int l, int r) {
		int p = lg[r - l + 1];
		return a[mx[p][l]] > a[mx[p][r - (1 << p) + 1]] ? 
			mx[p][l] : mx[p][r - (1 << p) + 1];
	}
	inline int query (int l, int r) { return a[queryp (l, r)]; }
} a;
int n, q;
map < pair < int, int >, ll > mp; 
int h[N];
ll DFS (int l, int r) {
	if (l > r) return 0;
	if (mp.count({l, r})) return mp[{l, r}];
	if (l == r) return h[l];
	int mi = a.queryp(l, r);
	return mp[{l, r}] = min(DFS(l, mi - 1) + (ll) (r - mi + 1) * h[mi], 
		DFS(mi + 1, r) + (ll) (mi - l + 1) * h[mi]);
}

struct wk {
	bool op;
	inline int gmx(int l, int r) {
		return op ? n - a.queryp(n - r + 1, n - l + 1) + 1 : a.queryp (l, r);
	}
	int h[N], stk[N], tp, fa[N], dep[N];
	ll fw[N], all[N];
	vi e[N];
	int dfn[N], MP[N], hv[N], siz[N], mxto[N], idt;
	struct line {
		int k;
		ll b;
		line (int K = 0, ll B = 0) {
			k = K, b = B;
		}
		inline ll get (int w) {
			return b + (ll) k * w;
		}
	}; 
	ll inter (line u, line v) {
		return (u.b - v.b) / (v.k - u.k);
	}
	
	int hd[1 << 21], ch[M][2], tot, seg[M];
	line f[N];
	void Add(int &id, int L, int R, int p) {
		ll nl = f[seg[id]].get(L), nr = f[seg[id]].get(R), pl = f[p].get(L), pr = f[p].get(R);
		if(id && nl <= pl && nr <= pr) return;
		int x = ++tot;
		ch[x][0] = ch[id][0], ch[x][1] = ch[id][1], seg[x] = seg[id]; 
		if(!id || (nl >= pl && nr >= pr)) return seg[x] = p, id = x, void();
		id = x;
		int mid = (L + R) >> 1;
		ll it = inter(f[seg[x]], f[p]);
		if(it <= mid) {
			if(nl <= pl) Add(ch[x][0], L, mid, seg[x]), seg[x] = p;
			else Add(ch[x][0], L, mid, p);
		}
		else {
			if(nl <= pl) Add(ch[x][1], mid + 1, R, p);
			else Add(ch[x][1], mid + 1, R, seg[x]), seg[x] = p;
		}
	}
	ll Qry(int id, int L, int R, int pos) {
		if(!id) return inf;
		if(L == R) return f[seg[id]].get(pos);
		int mid = (L + R) >> 1;
		if(pos <= mid) return min(f[seg[id]].get(pos), Qry(ch[id][0], L, mid, pos));
		else return min(f[seg[id]].get(pos), Qry(ch[id][1], mid + 1, R, pos));
	}
	int merge (int x, int y, int L, int R) {
		if(!x || !y) return x | y;
		int nw = ++tot, mid = (L + R) >> 1;
		ch[nw][0] = merge(ch[x][0], ch[y][0], L, mid);
		ch[nw][1] = merge(ch[x][1], ch[y][1], mid + 1, R);
		seg[nw] = seg[x];
		Add (nw, L, R, seg[y]);
		return nw;
	}
	void Build (int x, int L, int R) {
		if(L == R) 
			return f[L] = line (-h[MP[L]], fw[MP[L]]), hd[x] = ++tot, seg[hd[x]] = L, void ();
		int mid = (L + R) >> 1;
		Build (x << 1, L, mid);
		Build (x << 1 | 1, mid + 1, R);
		hd[x] = merge (hd[x << 1], hd[x << 1 | 1], 1, n);
	}
	ll query (int x, int L, int R, int l, int r, int p) {
		if(l <= L && R <= r) return Qry (hd[x], 1, n, p);
		int mid = (L + R) >> 1;
		ll ret = inf;
		if(l <= mid) ret = min(ret, query (x << 1, L, mid, l, r, p));
		if(r > mid) ret = min(ret, query (x << 1 | 1, mid + 1, R, l, r, p));
		return ret;
	}
	
	void dfs (int x) {
		siz[x] = 1;
		for (auto v : e[x]) {
			dep[v] = dep[x] + 1, dfs(v), siz[x] += siz[v];
			if(siz[v] > siz[hv[x]]) hv[x] = v;
		}
	}
	
	void dfs2(int x) {
		dfn[x] = ++idt;
		MP[idt] = x;
		if(hv[x]) mxto[hv[x]] = mxto[x], dfs2 (hv[x]);
		for (auto v : e[x]) if(v != hv[x]) mxto[v] = v, dfs2 (v);
	}
	
	void init () {
		L(i, 1, n) {
			while (tp > 0 && h[i] >= h[stk[tp]] + op) fa[stk[tp]] = i, -- tp;
			stk[++tp] = i;
		}
		R(i, n, 1) if(fa[i]) 
			all[i] = (ll) (fa[i] - i) * h[i] + all[fa[i]], 
		fw[i] = (op ? DFS(n - (fa[i] - 1) + 1, n - i + 1) : DFS(i, fa[i] - 1)) + all[fa[i]];
		L(i, 1, n) fw[i] += (ll) h[i] * i;
		L(i, 1, n) if(fa[i]) e[fa[i]].push_back(i);
		R(i, n, 1) if(!dfn[i]) dfs (i), mxto[i] = i, dfs2 (i);
		Build (1, 1, n);
	}
	ll query (int l, int r) { // r : max
		if(l == r) return 0;
		ll ns = 1e18;
		int u = l;
		for (; mxto[u] != mxto[r]; u = fa[mxto[u]]) 
			ns = min(ns, query (1, 1, n, dfn[mxto[u]], dfn[u], l));
		if(dfn[r] < dfn[u]) ns = min(ns, query (1, 1, n, dfn[r] + 1, dfn[u], l));
//		for (int u = l; u != r; u = fa[u]) ns = min(ns, fw[u] - (ll) h[u] * l);
		return ns - all[r];
	}
} u, v;
vector < ll > minimum_costs (vi H, vi L, vi R) {
	n = sz(H), q = sz(L);
	L(i, 1, n) h[i] = H[i - 1], u.h[i] = v.h[n - i + 1] = h[i], a.a[i] = h[i];
	a.init(n);
	v.op = true;
	u.init(), v.init();
	vector < ll > ns (q);
	L(t, 0, q - 1) {
		int l = L[t], r = R[t];
		++ l, ++ r;
		int p = a.queryp(l, r);
		ns[t] = min(u.query(l, p) + (ll) h[p] * (r - p + 1), 
		v.query(n - r + 1, n - p + 1) + (ll) h[p] * (p - l + 1));
	}
	return ns;
} 

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