Submission #795107

#	Time	Username	Problem	Language	Result	Execution time	Memory
795107		ymm	Meetings (IOI18_meetings)	C++17	100 / 100	2441 ms	479456 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1e6+10;

ll eval(const pll &f, ll x) { return f.first * x + f.second; }

namespace seg {
	struct node {
		pll val;
		ll lzy;
		ll fst, lst;
		bool leaf;
	} t[N*4];
	int sz;

	void init(int n) {
		sz = n;
		t[0].val = {};
		t[0].lzy = 0;
		t[0].fst = 0;
		t[0].lst = 0;
		t[0].leaf = 1;
	}

	void up(int i, ll x) {
		t[i].val.second += x;
		t[i].lzy += x;
		t[i].fst += x;
		t[i].lst += x;
	}
	void ppg(int i, int b, int e) {
		if (t[i].leaf) {
			t[2*i+1] = t[2*i+2] = t[i];
			t[2*i+1].lst = eval(t[2*i+1].val, (b+e)/2-1);
			t[2*i+2].fst = eval(t[2*i+2].val, (b+e)/2);
			t[i].leaf = 0;
		} else {
			up(2*i+1, t[i].lzy);
			up(2*i+2, t[i].lzy);
		}
		t[i].lzy = 0;
	}

	void merge(int i) {
		t[i].fst = t[2*i+1].fst;
		t[i].lst = t[2*i+2].lst;
	}

	void add(int l, int r, ll x, int i, int b, int e) {
		if (l <= b && e <= r) {
			up(i, x);
			return;
		}
		ppg(i, b, e);
		if (l < (b+e)/2)
			add(l, r, x, 2*i+1, b, (b+e)/2);
		if ((b+e)/2 < r)
			add(l, r, x, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void add(int l, int r, ll x) { add(l, r, x, 0, 0, sz); }

	void mn(int l, int r, pll f, int i, int b, int e) {
		ll fst2 = eval(f, b);
		ll lst2 = eval(f, e-1);
		if (l <= b && e <= r && t[i].fst >= fst2 && t[i].lst >= lst2) {
			t[i].val = f;
			t[i].fst = fst2;
			t[i].lst = lst2;
			t[i].leaf = 1;
			return;
		}
		if (l <= b && e <= r && t[i].lst <= lst2 && t[i].fst <= fst2)
			return;
		ppg(i, b, e);
		if (l < (b+e)/2)
			mn(l, r, f, 2*i+1, b, (b+e)/2);
		if ((b+e)/2 < r)
			mn(l, r, f, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void mn(int l, int r, pll f) { mn(l, r, f, 0, 0, sz); }

	ll get(int p, int i, int b, int e) {
		if (t[i].leaf)
			return eval(t[i].val, p);
		ppg(i, b, e);
		if (p < (b+e)/2)
			return get(p, 2*i+1, b, (b+e)/2);
		else
			return get(p, 2*i+2, (b+e)/2, e);
	}
	ll get(int p) { return get(p, 0, 0, sz); }
}

namespace rmq {
	const int lg = 20;
	pii mx[lg][N];

	void make(vector<int> a) {
		int n = a.size();
		Loop (i,0,n)
			mx[0][i] = {a[i], i};
		Loop (i,0,lg-1) {
			for (int j = 0; j + (2 << i) <= n; ++j)
				mx[i+1][j] = max(mx[i][j], mx[i][j+(1<<i)]);
		}
	}

	pii get(int l, int r) {
		int k = __lg(r-l);
		return max(mx[k][l], mx[k][r-(1<<k)]);
	}
}

ll arr[N];

namespace cart {
	pii t[N];
	vector<pair<ll *, int>> queryl[N];
	vector<pair<ll *, int>> queryr[N];
	int rt;
	int sz;

	void make(int &ans, int l, int r) {
		if (l >= r) {
			ans = -1;
			return;
		}
		ans = rmq::get(l, r).second;
		make(t[ans].first, l, ans);
		make(t[ans].second, ans+1, r);
	}
	void make(int n) { sz = n; make(rt, 0, sz); }

	void dfs(int v, int l, int r, void (*merge)(int, int, int)) {
		if (v == -1)
			return;
		dfs(t[v].first, l, v, merge);
		dfs(t[v].second, v+1, r, merge);
		merge(v, l, r);
	}

	void mergel(int v, int l, int r) {
		seg::add(v, r, (v-l+1)*arr[v]);
		if (v != l) {
			ll x = seg::get(v-1);
			seg::mn(v, r, pll{arr[v], x - (v-1)*arr[v]});
		}
		for (auto [p, pos] : queryl[v])
			*p = seg::get(pos);
	}
	void merger(int v, int l, int r) {
		seg::add(l, v+1, (r-v)*arr[v]);
		if (v != r-1) {
			ll x = seg::get(v+1);
			seg::mn(l, v+1, pll{-arr[v], x + (v+1)*arr[v]});
		}
		for (auto [p, pos] : queryr[v])
			*p = seg::get(pos);
	}

	void answer() {
		seg::init(sz);
		dfs(rt, 0, sz, mergel);
		seg::init(sz);
		dfs(rt, 0, sz, merger);
	}
}

ll Ql[N], Qr[N];

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	int n = H.size();
	Loop (i,0,n)
		arr[i] = H[i];
	rmq::make(H);
	cart::make(n);
	int q = L.size();
	Loop (i,0,q) {
		int l = L[i];
		int r = R[i]+1;
		int v = rmq::get(l, r).second;
		if (l < v) {
			cart::queryr[cart::t[v].first]
				.push_back({&Ql[i], l});
		}
		if (v < r-1) {
			cart::queryl[cart::t[v].second]
				.push_back({&Qr[i], r-1});
		}
	}
	cart::answer();
	vector<ll> ans(q);
	Loop (i,0,q) {
		int l = L[i];
		int r = R[i]+1;
		int v = rmq::get(l, r).second;
		ans[i] = arr[v] * (r-l);
		if (l < v)
			ans[i] = min(ans[i], Ql[i] + arr[v] * (r-v));
		if (v < r-1)
			ans[i] = min(ans[i], Qr[i] + arr[v] * (v-l+1));
	}
	return ans;
}

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