Submission #817619

#	Time	Username	Problem	Language	Result	Execution time	Memory
817619		NothingXD	Meetings (IOI18_meetings)	C++17	60 / 100	5545 ms	351780 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e6 + 10;

struct Seg{
	ll l, r;
};

pll lazy1[maxn << 2];
ll lazy2[maxn << 2];
Seg seg[maxn << 2];

void merge(int v)
{
	seg[v].l = seg[v << 1].l;
	seg[v].r = seg[v << 1 | 1].r;
}

//void shift(int v, int l, int r);

void update1(int v, int l, int r, ll a, ll b){
	seg[v].l = a + b * l;
	seg[v].r = a + b * (r-1);
	lazy1[v] = {a, b};
}

void update2(int v, int l, int r, ll val){
	seg[v].l += val;
	seg[v].r += val;
	lazy1[v].F += val;
	lazy2[v] += val;
}


void shift(int v, int l, int r){
	if (lazy2[v] == 0 && lazy1[v].S == -1) return;
	int mid = (l + r) >> 1;
	if (lazy2[v] != 0){
		update2(v << 1, l, mid, lazy2[v]);
		update2(v << 1 | 1, mid, r, lazy2[v]);
	}
	if (lazy1[v].S != -1){
		update1(v << 1, l, mid, lazy1[v].F, lazy1[v].S);
		update1(v << 1 | 1, mid, r, lazy1[v].F, lazy1[v].S);
	}
	lazy1[v] = {0, -1};
	lazy2[v] = 0;
}

void change(int v, int l, int r, int ql, int qr, ll a, ll b){
//	if (v == 1) debug(ql, qr, a, b);
	if (qr <= l || r <= ql) return;
	if (!(ql <= l && r <= qr)){
		shift(v, l, r);
		int mid = (l + r) >> 1;
		change(v << 1, l, mid, ql, qr, a, b);
		change(v << 1 | 1, mid, r, ql, qr, a, b);
	}
	else{
	//	debug(v, l, r, ql, qr, a, b, seg[v].l, seg[v].r);
		if (a + b * l <= seg[v].l && a + b * (r-1) <= seg[v].r){
	//		debug(seg[v].l, seg[v].r, seg[v].mx, lazy1[v].F, lazy1[v].S);
			update1(v, l, r, a, b);
			return;
		}
		if (a + b * l >= seg[v].l && a + b * (r-1) >= seg[v].r) return;
		shift(v, l, r);
		int mid = (l + r) >> 1;
		change(v << 1, l, mid, ql, qr, a, b);
		change(v << 1 | 1, mid, r, ql, qr, a, b);
	}
	merge(v);
	//seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

void add(int v, int l, int r, int ql, int qr, ll val){
	//if (v == 1) debug(ql, qr, val);
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
//		debug(v, l, r, ql, qr, val);
		update2(v, l, r, val);
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	add(v << 1, l, mid, ql, qr, val);
	add(v << 1 | 1, mid, r, ql, qr, val);
	merge(v);
	//seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

ll get(int v, int l, int r, int idx){
	//if (v == 1) debug(idx);
	if (l + 1 == r) return seg[v].l;
	shift(v, l, r);
	int mid = (l + r) >> 1;
	if (idx < mid) return get(v << 1, l, mid, idx);
	else return get(v << 1 | 1, mid, r, idx);
}


const int lg = 20;
const ll inf = 1e18;

int n, q, h[maxn], queryl[maxn], queryr[maxn];
ll ans[maxn];
pii rmq[lg][maxn];
vector<pair<pii,int>> Q[maxn];

pii getmx(int l, int r){
	r++;
	int x = 31 - __builtin_clz(r-l);
	return max(rmq[x][l], rmq[x][r-(1<<x)]);
}

void solve(bool flg){
	vector<pii> val;
	for (int i = 0; i < n; i++){
		Q[i].clear();
	}
	for (int i = 1; i < 4*maxn; i++){
		seg[i] = {0, 0};
		lazy1[i] = {0, -1};
		lazy2[i] = 0;
	}
	for (int i = 0; i < n; i++){
		if (!flg){
			val.push_back({h[i], i});
			rmq[0][i] = {h[i], i};
		}
		else{
			val.push_back({h[i], -i});
			rmq[0][i] = {h[i], -i};
		}
	}
	for (int i = 1; i < lg; i++){
		for (int j = 0; j + (1 << i) <= n; j++){
			rmq[i][j] = max(rmq[i-1][j], rmq[i-1][j+(1<<(i-1))]);
		}
	}
	for (int i = 0; i < q; i++){
		int mx = abs(getmx(queryl[i], queryr[i]).S);
		Q[mx].push_back({{queryl[i], queryr[i]}, i});
	}
	sort(all(val));
	for (auto [x, y]: val){
		y = abs(y);
//		debug(x, y);
		for (auto [tmp, idx]: Q[y]){
			ans[idx] = min(ans[idx], get(1, 0, n, tmp.S) + 1ll * (y-tmp.F+1) * x);
		}
		int l = -1, r = y;
		while(l + 1 < r){
			int mid = (l + r) >> 1;
			if (abs(getmx(mid, y).S) == y) r = mid;
			else l = mid;
		}
		int l2 = y, r2 = n;
		while(l2 + 1 < r2){
			int mid = (l2 + r2) >> 1;
			if (abs(getmx(y, mid).S) == y) l2 = mid;
			else r2 = mid;
		}
		add(1, 0, n, y, r2, 1ll * (y-l) * x);
		if (r == y) continue;
		ll tmp = get(1, 0, n, y-1);
		tmp -= 1ll * (y-1) * x;
		change(1, 0, n, y, r2, tmp, x);
	}
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	n = H.size();
	q = L.size();
	for (int i = 0; i < n; i++){
		h[i] = H[i];
	}
	for (int i = 0; i < q; i++){
		queryl[i] = L[i];
		queryr[i] = R[i];
		ans[i] = inf;
	}
	solve(false);
//	debug("----------------");
//	for (int i = 0; i < q; i++) debug(i, ans[i]);
	for (int i = 0; i < q; i++){
		queryl[i] = n-R[i]-1;
		queryr[i] = n-L[i]-1;
	}
	for (int i = 0; i < n/2; i++){
		swap(h[i], h[n-i-1]);
	}
	solve(true);
	vector<ll> res;
	for (int i = 0; i < q; i++) res.push_back(ans[i]);
	return res;
}

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