oj.uz

Submission #75020

# Submission time Handle Problem Language Result Execution time Memory
75020 2018-09-08T04:04:09 Z ainta Meetings (IOI18_meetings) C++17
100 / 100
 4543 ms 364784 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 552 KB Output is correct
2 Correct 8 ms 1124 KB Output is correct
3 Correct 8 ms 1116 KB Output is correct
4 Correct 8 ms 1116 KB Output is correct
5 Correct 8 ms 1152 KB Output is correct
6 Correct 8 ms 1372 KB Output is correct
7 Correct 8 ms 1120 KB Output is correct
8 Correct 7 ms 1500 KB Output is correct
9 Correct 7 ms 1324 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 552 KB Output is correct
2 Correct 8 ms 1124 KB Output is correct
3 Correct 8 ms 1116 KB Output is correct
4 Correct 8 ms 1116 KB Output is correct
5 Correct 8 ms 1152 KB Output is correct
6 Correct 8 ms 1372 KB Output is correct
7 Correct 8 ms 1120 KB Output is correct
8 Correct 7 ms 1500 KB Output is correct
9 Correct 7 ms 1324 KB Output is correct
10 Correct 19 ms 2296 KB Output is correct
11 Correct 18 ms 2216 KB Output is correct
12 Correct 19 ms 2268 KB Output is correct
13 Correct 17 ms 2268 KB Output is correct
14 Correct 20 ms 2632 KB Output is correct
15 Correct 20 ms 2244 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 84 ms 5756 KB Output is correct
3 Correct 483 ms 37020 KB Output is correct
4 Correct 436 ms 29456 KB Output is correct
5 Correct 354 ms 36116 KB Output is correct
6 Correct 382 ms 38100 KB Output is correct
7 Correct 446 ms 44840 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 84 ms 5756 KB Output is correct
3 Correct 483 ms 37020 KB Output is correct
4 Correct 436 ms 29456 KB Output is correct
5 Correct 354 ms 36116 KB Output is correct
6 Correct 382 ms 38100 KB Output is correct
7 Correct 446 ms 44840 KB Output is correct
8 Correct 458 ms 29960 KB Output is correct
9 Correct 380 ms 29944 KB Output is correct
10 Correct 396 ms 30044 KB Output is correct
11 Correct 467 ms 29272 KB Output is correct
12 Correct 373 ms 29284 KB Output is correct
13 Correct 396 ms 29312 KB Output is correct
14 Correct 489 ms 37056 KB Output is correct
15 Correct 454 ms 29272 KB Output is correct
16 Correct 445 ms 44920 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 552 KB Output is correct
2 Correct 8 ms 1124 KB Output is correct
3 Correct 8 ms 1116 KB Output is correct
4 Correct 8 ms 1116 KB Output is correct
5 Correct 8 ms 1152 KB Output is correct
6 Correct 8 ms 1372 KB Output is correct
7 Correct 8 ms 1120 KB Output is correct
8 Correct 7 ms 1500 KB Output is correct
9 Correct 7 ms 1324 KB Output is correct
10 Correct 19 ms 2296 KB Output is correct
11 Correct 18 ms 2216 KB Output is correct
12 Correct 19 ms 2268 KB Output is correct
13 Correct 17 ms 2268 KB Output is correct
14 Correct 20 ms 2632 KB Output is correct
15 Correct 20 ms 2244 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 84 ms 5756 KB Output is correct
18 Correct 483 ms 37020 KB Output is correct
19 Correct 436 ms 29456 KB Output is correct
20 Correct 354 ms 36116 KB Output is correct
21 Correct 382 ms 38100 KB Output is correct
22 Correct 446 ms 44840 KB Output is correct
23 Correct 458 ms 29960 KB Output is correct
24 Correct 380 ms 29944 KB Output is correct
25 Correct 396 ms 30044 KB Output is correct
26 Correct 467 ms 29272 KB Output is correct
27 Correct 373 ms 29284 KB Output is correct
28 Correct 396 ms 29312 KB Output is correct
29 Correct 489 ms 37056 KB Output is correct
30 Correct 454 ms 29272 KB Output is correct
31 Correct 445 ms 44920 KB Output is correct
32 Correct 4181 ms 229252 KB Output is correct
33 Correct 3406 ms 248060 KB Output is correct
34 Correct 3362 ms 245864 KB Output is correct
35 Correct 4303 ms 248228 KB Output is correct
36 Correct 3359 ms 248220 KB Output is correct
37 Correct 3401 ms 246100 KB Output is correct
38 Correct 4543 ms 306564 KB Output is correct
39 Correct 4490 ms 306452 KB Output is correct
40 Correct 4355 ms 253796 KB Output is correct
41 Correct 3705 ms 362420 KB Output is correct
42 Correct 4215 ms 364784 KB Output is correct
43 Correct 4276 ms 364652 KB Output is correct
44 Correct 4417 ms 306168 KB Output is correct