Submission #75020

#	Time	Username	Problem	Language	Result	Execution time	Memory
75020		ainta	Meetings (IOI18_meetings)	C++17	100 / 100	4543 ms	364784 KiB

meetings

#include "meetings.h"
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define lint long long
#define SZ 1048576
#define N_ 751000

vector<lint>Res;

int w[N_], PV[N_], XX[N_], QL[N_], QR[N_];

int n, Q;

struct Query {
	int x, y, num;
	bool operator < (const Query &p)const {
		return x < p.x;
	}
}QQ[N_];

struct Tree {
	struct T1{
		lint AK, BK, AA, BB, CK;
		void Add(lint A, lint B) {
			AK += A;
			AA += A;
			BK += B;
			BB += B;
		}
		void Clear() {
			AK = BK = AA = BB = 0;
			CK = 1;
		}
	}L, R;
}IT[SZ + SZ];


void Add2(int nd, lint A1, lint B1, lint A2, lint B2) {
	IT[nd].L.Add(A1, B1);
	IT[nd].R.Add(A2, B2);
}
void Spread(int nd) {
	if (IT[nd].L.CK) {
		IT[nd * 2].L.Clear();
		IT[nd * 2 + 1].L.Clear();
		IT[nd].L.CK = 0;
	}
	if (IT[nd].R.CK) {
		IT[nd * 2].R.Clear();
		IT[nd * 2 + 1].R.Clear();
		IT[nd].R.CK = 0;
	}
	Add2(nd * 2, IT[nd].L.AK, IT[nd].L.BK, IT[nd].R.AK, IT[nd].R.BK);
	Add2(nd * 2 + 1, IT[nd].L.AK, IT[nd].L.BK, IT[nd].R.AK, IT[nd].R.BK);
	IT[nd].L.AK = IT[nd].L.BK = IT[nd].R.AK = IT[nd].R.BK = 0;
}
void UDT(int nd) {
	IT[nd].L.AA = IT[nd * 2].L.AA;
	IT[nd].L.BB = IT[nd * 2].L.BB;
	IT[nd].R.AA = IT[nd * 2 + 1].R.AA;
	IT[nd].R.BB = IT[nd * 2 + 1].R.BB;
}
void Add(int nd, int b, int e, int s, int l, lint A1, lint B1, lint A2, lint B2) {
	if (s > l)return;
	if (b == s && e == l) {
		Add2(nd, A1, B1, A2, B2);
		return;
	}
	int m = (b + e) >> 1;
	Spread(nd);
	if(s <= m)Add(nd * 2, b, m, s, min(m, l), A1, B1, A2, B2);
	if(l > m)Add(nd * 2 + 1, m + 1, e, max(m + 1, s), l, A1, B1, A2, B2);
	UDT(nd);
}

void Wipe(int nd, int b, int e, int s, int l, int ck) {
	if (s > l)return;
	if (b == s && e == l) {
		if (ck == 0)IT[nd].L.Clear();
		else IT[nd].R.Clear();
		return;
	}
	int m = (b + e) >> 1;
	Spread(nd);
	Wipe(nd * 2, b, m, s, min(m, l), ck);
	Wipe(nd * 2 + 1, m + 1, e, max(m + 1, s), l, ck);
	UDT(nd);
}

lint Calc(int nd, int b, int e, int x, int ck) {
	if (b == e) {
		if (ck == 0)return IT[nd].L.AA*x + IT[nd].L.BB;
		else return IT[nd].R.AA*x + IT[nd].R.BB;
	}
	int m = (b + e) >> 1;
	Spread(nd);
	if (x <= m)return Calc(nd * 2, b, m, x, ck);
	else return Calc(nd * 2 + 1, m + 1, e, x, ck);
}

int Rres, Lres;

void GetRight(int nd, int b, int e, int s, int l, lint M) {
	if (b == e) {
		if (IT[nd].R.AA * e + IT[nd].R.BB >= M)Rres = e;
		return;
	}
	int m = (b + e) >> 1;
	Spread(nd);
	if (l <= m)return GetRight(nd * 2, b, m, s, l, M);
	if (s > m)return GetRight(nd * 2 + 1, m + 1, e, s, l, M);
	if (IT[nd * 2].R.AA * m + IT[nd * 2].R.BB >= M) {
		Rres = m;
		GetRight(nd * 2, b, m, s, m, M);
	}
	else {
		GetRight(nd * 2 + 1, m + 1, e, m + 1, l, M);
	}
}

void GetLeft(int nd, int b, int e, int s, int l, lint M) {
	if (b == e) {
		if (IT[nd].L.AA * e + IT[nd].L.BB >= M)Lres = e;
		return;
	}
	int m = (b + e) >> 1;
	Spread(nd);
	if (l <= m)return GetLeft(nd * 2, b, m, s, l, M);
	if (s > m)return GetLeft(nd * 2 + 1, m + 1, e, s, l, M);
	if (IT[nd * 2 + 1].L.AA * (m + 1) + IT[nd * 2 + 1].L.BB >= M) {
		Lres = m + 1;
		GetLeft(nd * 2 + 1, m + 1, e, m + 1, l, M);
	}
	else {
		GetLeft(nd * 2, b, m, s, m, M);
	}
}


int GetRight2(int s, int l, lint M) {
	Rres = l + 1;
	GetRight(1, 1, n, s, l, M);
	return Rres;
}

int GetLeft2(int s, int l, lint M) {
	Lres = s - 1;
	GetLeft(1, 1, n, s, l, M);
	return Lres;
}

void Make(int s, int l, lint g, int ck) {
	Wipe(1, 1, n, s, l, ck);
	if(ck == 0)Add(1, 1, n, s, l, 0, g, 0, 0);
	else Add(1, 1, n, s, l, 0, 0, 0, g);
}


struct RMQ {
	int IT[SZ + SZ];
	void Put(int a, int h) {
		a += SZ;
		IT[a] = h;
		while (a != 1) {
			a >>= 1;
			IT[a] = max(IT[a * 2], IT[a * 2 + 1]);
		}
	}
	int Find(int b, int e) {
		int r = -1, pv = 0;
		b += SZ, e += SZ;
		while (b <= e) {
			if (r < IT[b])r = IT[b], pv = b;
			if (r < IT[e])r = IT[e], pv = e;
			b = (b + 1) >> 1, e = (e - 1) >> 1;
		}
		while (pv < SZ) {
			pv *= 2;
			if (IT[pv] != r)pv++;
		}
		return pv - SZ;
	}
}HH, TP;

int Do(int b, int e) {

	int m = HH.Find(b, e);
	int ret = w[m];
	lint M = w[m], LM = 0, RM = 0;
	if (b != m) {
		LM = Do(b, m - 1);
	}
	if (e != m) {
		RM = Do(m + 1, e);
	}

	int p1 = lower_bound(XX, XX + Q, m) - XX;
	int p2 = lower_bound(XX, XX + Q, e + 1) - XX;

	while (p1 < p2) {
		int t = TP.Find(p1, p2 - 1);
		if (TP.IT[t + SZ] < b)break;
		int x = QQ[t].num;
		TP.Put(t, 0);

		int bb = QL[x], ee = QR[x];
		lint rr = 0;
		if (bb != m) {
			rr = max(rr, (M - LM) * (m - bb) + Calc(1, 1, n, bb, 0));
		}
		if (ee != m) {
			rr = max(rr, (M - RM) * (ee - m) + Calc(1, 1, n, ee, 1));
		}
		Res[x] = M * (ee - bb + 1) - rr;
	}

	Add(1, 1, n, m + 1, e, -(M - RM), (e + 1) * (M - RM), (M - RM), -m * (M - RM));
	Add(1, 1, n, b, m - 1, -(M - LM), m * (M - LM), (M - LM), -(b - 1) * (M - LM));

	if (e > m) {

		lint Lg = Calc(1, 1, n, m + 1, 0);
		int pv;
		if (b < m)pv = GetLeft2(b, m - 1, Lg);
		else pv = m - 1;
		Make(pv + 1, m, Lg, 0);
	}


	if (b < m) {
		lint Rg = Calc(1, 1, n, m - 1, 1);
		int pv;
		if (e > m)pv = GetRight2(m + 1, e, Rg);
		else pv = m + 1;
		Make(m, pv - 1, Rg, 1);
	}

	return ret;
}

std::vector<lint> minimum_costs(std::vector<int> H, std::vector<int> L,
	std::vector<int> R) {
	Q = L.size();
	n = H.size();
	int i;
	Res.resize(Q);
	for (i = 0; i < Q; i++) {
		QQ[i] = { R[i] + 1,L[i] + 1,i };
		QL[i] = L[i] + 1, QR[i] = R[i] + 1;
	}
	sort(QQ, QQ + Q);
	for (i = 0; i < Q; i++)XX[i] = QQ[i].x;

	for (i = 0; i < n; i++)w[i + 1] = H[i];
	for (i = 1; i <= n; i++) {
		HH.Put(i, w[i]);
	}
	for (i = 0; i < Q; i++) {
		TP.Put(i, QQ[i].y);
	}
	Do(1, n);
	return Res;
}

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