oj.uz

Submission #140605

# Submission time Handle Problem Language Result Execution time Memory
140605 2019-08-03T16:45:17 Z eriksuenderhauf Meetings (IOI18_meetings) C++11
100 / 100
 5351 ms 306760 KB 
//#pragma GCC optimize("O3")
//#include "meetings.h"
#include <bits/stdc++.h>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const ll INF = 1e18 + 7;
const int MAXN = 75e4 + 5;
const double eps = 1e-9;
int n, q;
vi qryL, qryR;
pii sp[20][MAXN];
vl ans;
vi adj[MAXN];
pll seg[MAXN*4], lz[MAXN*4];

int qry(int l, int r) {
	int x = 31 - __builtin_clz(r-l+1);
	return max(sp[x][l],sp[x][r-(1<<x)+1]).se;
}

void prop(ll l, ll r, int k) {
	if (l != r) {
		if (lz[k].fi) {
			lz[k*2] = mp(lz[k].fi, 0ll);
			lz[k*2+1] = mp(lz[k].fi, 0ll);
		}
		lz[k*2].se += lz[k].se;
		lz[k*2+1].se += lz[k].se;
	}
	if (lz[k].fi) seg[k] = mp(l*lz[k].fi,r*lz[k].fi);
	seg[k].fi += lz[k].se;
	seg[k].se += lz[k].se;
	lz[k] = mp(0ll,0ll);
}

void upd(int l, int r, int k, int a, int b, pll v, bool fl) {
	if (lz[k] != mp(0ll,0ll)) prop(l,r,k);
	if (r < a || b < l) return;
	if (a <= l && r <= b) {
		if (fl || r * v.fi + v.se < seg[k].se) {
			lz[k] = v;
			prop(l,r,k);
			return;
		}
		if (seg[k].fi <= l * v.fi + v.se)
			return;
	}
	int m = (l+r) / 2;
	upd(l,m,k*2,a,b,v,fl);
	upd(m+1,r,k*2+1,a,b,v,fl);
	seg[k] = mp(seg[k*2].fi, seg[k*2+1].se);
}

ll qrySeg(int l, int r, int k, int a) {
	if (lz[k] != mp(0ll,0ll)) prop(l,r,k);
	if (r < a || a < l) return -INF;
	if (a <= l && r <= a) return seg[k].fi;
	int m = (l+r) / 2;
	return max(qrySeg(l,m,k*2,a),qrySeg(m+1,r,k*2+1,a));
}

int solve(int l, int r) {
	if (r < l) return -1;
	int ind = abs(qry(l,r));
	int l2 = solve(l,ind-1), r2 = solve(ind+1,r);
	upd(0, n-1, 1, ind, ind, mp(1, -ind), 1);
	for (int v: adj[ind])
		ans[v] = min(ans[v], qrySeg(0,n-1,1,qryR[v]) + (ind-qryL[v]+1ll)*sp[0][ind].fi);
	upd(0, n-1, 1, ind, r, mp(0, (ind-l+1ll) * sp[0][ind].fi), 1);
	upd(0, n-1, 1, ind, r, mp(sp[0][ind].fi, (l2 != -1 ? qrySeg(0,n-1,1,ind-1) : 0ll) - (ind-1ll) * sp[0][ind].fi), 0);
	return ind;
}

vl minimum_costs(vi h, vi l, vi r) {
	n = h.size(), q = l.size();
	for (int i = 0; i < q; i++) {
		qryL.pb(l[i]);
		qryR.pb(r[i]);
		ans.pb(INF);
	}
	for (int i = 0; i < n; i++)
		sp[0][i] = mp(h[i], i);
	for (int i = 1; i < 20; i++)
		for (int j = 0; j <= n-(1<<i); j++)
			sp[i][j] = max(sp[i-1][j], sp[i-1][j+(1<<(i-1))]);
	for (int i = 0; i < q; i++)
		adj[qry(qryL[i],qryR[i])].pb(i);
	solve(0, n-1);
	reverse(adj, adj + n);
	for (int i = 0; i < q; i++)
		tie(qryL[i], qryR[i]) = mp(n-qryR[i]-1,n-qryL[i]-1);
	for (int i = 0; i < n; i++)
		sp[0][i] = mp(h[n-i-1], -i);
	for (int i = 1; i < 20; i++)
		for (int j = 0; j <= n-(1<<i); j++)
			sp[i][j] = max(sp[i-1][j], sp[i-1][j+(1<<(i-1))]);
	solve(0,n-1);
	return ans;
}

Compilation message

meetings.cpp: In function 'int solve(int, int)':
meetings.cpp:88:27: warning: unused variable 'r2' [-Wunused-variable]
  int l2 = solve(l,ind-1), r2 = solve(ind+1,r);
                           ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17884 KB Output is correct
2 Correct 25 ms 18612 KB Output is correct
3 Correct 25 ms 18500 KB Output is correct
4 Correct 25 ms 18620 KB Output is correct
5 Correct 25 ms 18524 KB Output is correct
6 Correct 24 ms 18728 KB Output is correct
7 Correct 26 ms 18616 KB Output is correct
8 Correct 25 ms 18768 KB Output is correct
9 Correct 25 ms 18632 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17884 KB Output is correct
2 Correct 25 ms 18612 KB Output is correct
3 Correct 25 ms 18500 KB Output is correct
4 Correct 25 ms 18620 KB Output is correct
5 Correct 25 ms 18524 KB Output is correct
6 Correct 24 ms 18728 KB Output is correct
7 Correct 26 ms 18616 KB Output is correct
8 Correct 25 ms 18768 KB Output is correct
9 Correct 25 ms 18632 KB Output is correct
10 Correct 36 ms 19384 KB Output is correct
11 Correct 35 ms 19328 KB Output is correct
12 Correct 35 ms 19416 KB Output is correct
13 Correct 34 ms 19448 KB Output is correct
14 Correct 35 ms 19600 KB Output is correct
15 Correct 35 ms 19332 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18000 KB Output is correct
2 Correct 94 ms 22048 KB Output is correct
3 Correct 503 ms 48432 KB Output is correct
4 Correct 455 ms 43992 KB Output is correct
5 Correct 487 ms 50324 KB Output is correct
6 Correct 479 ms 50480 KB Output is correct
7 Correct 500 ms 50700 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18000 KB Output is correct
2 Correct 94 ms 22048 KB Output is correct
3 Correct 503 ms 48432 KB Output is correct
4 Correct 455 ms 43992 KB Output is correct
5 Correct 487 ms 50324 KB Output is correct
6 Correct 479 ms 50480 KB Output is correct
7 Correct 500 ms 50700 KB Output is correct
8 Correct 469 ms 44340 KB Output is correct
9 Correct 407 ms 46324 KB Output is correct
10 Correct 439 ms 46396 KB Output is correct
11 Correct 465 ms 45956 KB Output is correct
12 Correct 408 ms 45960 KB Output is correct
13 Correct 435 ms 46052 KB Output is correct
14 Correct 503 ms 50496 KB Output is correct
15 Correct 445 ms 45956 KB Output is correct
16 Correct 517 ms 50632 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17884 KB Output is correct
2 Correct 25 ms 18612 KB Output is correct
3 Correct 25 ms 18500 KB Output is correct
4 Correct 25 ms 18620 KB Output is correct
5 Correct 25 ms 18524 KB Output is correct
6 Correct 24 ms 18728 KB Output is correct
7 Correct 26 ms 18616 KB Output is correct
8 Correct 25 ms 18768 KB Output is correct
9 Correct 25 ms 18632 KB Output is correct
10 Correct 36 ms 19384 KB Output is correct
11 Correct 35 ms 19328 KB Output is correct
12 Correct 35 ms 19416 KB Output is correct
13 Correct 34 ms 19448 KB Output is correct
14 Correct 35 ms 19600 KB Output is correct
15 Correct 35 ms 19332 KB Output is correct
16 Correct 19 ms 18000 KB Output is correct
17 Correct 94 ms 22048 KB Output is correct
18 Correct 503 ms 48432 KB Output is correct
19 Correct 455 ms 43992 KB Output is correct
20 Correct 487 ms 50324 KB Output is correct
21 Correct 479 ms 50480 KB Output is correct
22 Correct 500 ms 50700 KB Output is correct
23 Correct 469 ms 44340 KB Output is correct
24 Correct 407 ms 46324 KB Output is correct
25 Correct 439 ms 46396 KB Output is correct
26 Correct 465 ms 45956 KB Output is correct
27 Correct 408 ms 45960 KB Output is correct
28 Correct 435 ms 46052 KB Output is correct
29 Correct 503 ms 50496 KB Output is correct
30 Correct 445 ms 45956 KB Output is correct
31 Correct 517 ms 50632 KB Output is correct
32 Correct 4086 ms 239336 KB Output is correct
33 Correct 3408 ms 241992 KB Output is correct
34 Correct 3771 ms 238036 KB Output is correct
35 Correct 4430 ms 239392 KB Output is correct
36 Correct 3438 ms 240324 KB Output is correct
37 Correct 3788 ms 238168 KB Output is correct
38 Correct 4654 ms 273700 KB Output is correct
39 Correct 5035 ms 273756 KB Output is correct
40 Correct 4534 ms 243524 KB Output is correct
41 Correct 4880 ms 303424 KB Output is correct
42 Correct 5351 ms 306308 KB Output is correct
43 Correct 5344 ms 306760 KB Output is correct
44 Correct 5086 ms 273552 KB Output is correct