oj.uz

Submission #250883

# Submission time Handle Problem Language Result Execution time Memory
250883 2020-07-19T10:45:55 Z oolimry Meetings (IOI18_meetings) C++14
100 / 100
 3818 ms 467608 KB 
#include "meetings.h"
#include <bits/stdc++.h>
#define m first 
#define c second
using namespace std;
typedef pair<long long, long long> ii;
typedef pair<long long, long long> line;

const int MAXN = 750005;
const long long INF = 10234567890123456;
int n, Q;
static long long H[MAXN];

struct query {long long l, r, id;};
static vector<query> queries[MAXN];

struct segmenttree{
	ii tree[MAXN*2];
	void init(){
		for(int i = 0;i < n;i++) tree[i+n]= ii(H[i],i);
		for(int i = n-1;i >= 1;i--) tree[i] = max(tree[i<<1], tree[i<<1|1]);
	}
	int query(int l, int r){
		ii res = ii(0,0);
		for(l += n, r += n+1;l < r;l >>= 1, r >>= 1){
			if(l&1) res = max(res, tree[l++]);
			if(r&1) res = max(res, tree[--r]);
		}
		return res.second;
	}
} FINDMAX;


long long get(line L, long long x) { return L.m * x + L.c; }
struct lichao{
	int s, e, m;
	lichao *l, *r;
	line val = {0,INF};
	long long lazy = 0;
	
	lichao(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if(s != e){
			l = new lichao(s,m);
			r = new lichao(m+1,e);
		}
	}
	
	void push(){
		if(s == e) return;
		l->lazy += lazy;
		r->lazy += lazy;
		(l->val).c += lazy;
		(r->val).c += lazy;
		lazy = 0;
	}
	
	void insert(int S, int E, line L){
		if(s > E || S > e || S > E) return;
		push();
		
		if(S <= s && e <= E){
			if(get(L, m) < get(val, m)) swap(L, val); ///make val the dominant one
	
			if(s == e) return;
			if(get(L,s) >= get(val,s) && get(L,e) >= get(val,e)) return; ///L is redundant	
							
			if(get(L, s) < get(val, s)) l->insert(S, E, L); ///L has some chance in l
			else r->insert(S, E, L); ///L has some chance in r
		}
		else{
			l->insert(S, E, L);
			r->insert(S, E, L);
		}
	}
	
	void lazyAdd(int S, int E, long long V){
		push();
		if(s == S && e == E){
			lazy += V;
			val.c += V;
			return;
		}
		else if(E <= m) l->lazyAdd(S,E,V);
		else if(S >= m+1) r->lazyAdd(S,E,V);
		else{
			l->lazyAdd(S,m,V);
			r->lazyAdd(m+1,E,V);
		}
	}
	
	long long query(long long x){
		push();
		if(s == e) return get(val,x);
		if(x <= m) return min(get(val,x), l->query(x));
		else return min(get(val,x), r->query(x));
	}
		
} *Left, *Right;

vector<long long> ans;

void solve(long long L, long long R){
	if(L > R) return;
	long long M = FINDMAX.query(L, R);
	solve(L,M-1);
	solve(M+1,R);
	
	Left->insert(M, M, line(0,0));
	Right->insert(M, M, line(0,0));
	
	for(query q : queries[M]){
		ans[q.id] = min(Left->query(q.l) + (q.r - M + 1LL) * H[M], 
		                Right->query(q.r) + (M - q.l + 1LL) * H[M]);
	}
	
	Left->lazyAdd(L, M, (R - M + 1) * H[M]); ///meeting place left of M
	Left->insert(L, M, line(-H[M], (M+1) * H[M] + (R == M ? 0LL : Left->query(M+1) )) ); ///meeting place right of M
	
	Right->lazyAdd(M, R, (M - L + 1) * H[M]); ///meeting place right of M
	Right->insert(M, R, line(H[M], (1-M) * H[M] + (L == M ? 0LL : Right->query(M-1) )) );///meething place left of M
}

vector<long long> minimum_costs(vector<int> _H, vector<int> L, vector<int> R){
	n = _H.size();
	for(int i = 0;i < n;i++) H[i] = _H[i];
	Q = L.size();
	ans.resize(Q);
	
	FINDMAX.init();
	
	for(int i = 0;i < Q;i++){
		int m = FINDMAX.query(L[i],R[i]);
		queries[m].push_back({L[i],R[i],i});
	}
	
	Left = new lichao(0,n-1);
	Right = new lichao(0,n-1);
	
	solve(0, n-1);
	
	return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 17920 KB Output is correct
2 Correct 17 ms 18816 KB Output is correct
3 Correct 21 ms 18816 KB Output is correct
4 Correct 30 ms 18816 KB Output is correct
5 Correct 16 ms 18844 KB Output is correct
6 Correct 35 ms 19200 KB Output is correct
7 Correct 16 ms 18816 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 22 ms 19080 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 17920 KB Output is correct
2 Correct 17 ms 18816 KB Output is correct
3 Correct 21 ms 18816 KB Output is correct
4 Correct 30 ms 18816 KB Output is correct
5 Correct 16 ms 18844 KB Output is correct
6 Correct 35 ms 19200 KB Output is correct
7 Correct 16 ms 18816 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 22 ms 19080 KB Output is correct
10 Correct 36 ms 19924 KB Output is correct
11 Correct 23 ms 19896 KB Output is correct
12 Correct 37 ms 19960 KB Output is correct
13 Correct 24 ms 19840 KB Output is correct
14 Correct 31 ms 20480 KB Output is correct
15 Correct 23 ms 19840 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17920 KB Output is correct
2 Correct 71 ms 25208 KB Output is correct
3 Correct 349 ms 66552 KB Output is correct
4 Correct 340 ms 54648 KB Output is correct
5 Correct 290 ms 66424 KB Output is correct
6 Correct 311 ms 67832 KB Output is correct
7 Correct 361 ms 72240 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17920 KB Output is correct
2 Correct 71 ms 25208 KB Output is correct
3 Correct 349 ms 66552 KB Output is correct
4 Correct 340 ms 54648 KB Output is correct
5 Correct 290 ms 66424 KB Output is correct
6 Correct 311 ms 67832 KB Output is correct
7 Correct 361 ms 72240 KB Output is correct
8 Correct 350 ms 56184 KB Output is correct
9 Correct 275 ms 55392 KB Output is correct
10 Correct 290 ms 56056 KB Output is correct
11 Correct 337 ms 54776 KB Output is correct
12 Correct 285 ms 53860 KB Output is correct
13 Correct 312 ms 54908 KB Output is correct
14 Correct 358 ms 66556 KB Output is correct
15 Correct 342 ms 54328 KB Output is correct
16 Correct 370 ms 66808 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 17920 KB Output is correct
2 Correct 17 ms 18816 KB Output is correct
3 Correct 21 ms 18816 KB Output is correct
4 Correct 30 ms 18816 KB Output is correct
5 Correct 16 ms 18844 KB Output is correct
6 Correct 35 ms 19200 KB Output is correct
7 Correct 16 ms 18816 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 22 ms 19080 KB Output is correct
10 Correct 36 ms 19924 KB Output is correct
11 Correct 23 ms 19896 KB Output is correct
12 Correct 37 ms 19960 KB Output is correct
13 Correct 24 ms 19840 KB Output is correct
14 Correct 31 ms 20480 KB Output is correct
15 Correct 23 ms 19840 KB Output is correct
16 Correct 11 ms 17920 KB Output is correct
17 Correct 71 ms 25208 KB Output is correct
18 Correct 349 ms 66552 KB Output is correct
19 Correct 340 ms 54648 KB Output is correct
20 Correct 290 ms 66424 KB Output is correct
21 Correct 311 ms 67832 KB Output is correct
22 Correct 361 ms 72240 KB Output is correct
23 Correct 350 ms 56184 KB Output is correct
24 Correct 275 ms 55392 KB Output is correct
25 Correct 290 ms 56056 KB Output is correct
26 Correct 337 ms 54776 KB Output is correct
27 Correct 285 ms 53860 KB Output is correct
28 Correct 312 ms 54908 KB Output is correct
29 Correct 358 ms 66556 KB Output is correct
30 Correct 342 ms 54328 KB Output is correct
31 Correct 370 ms 66808 KB Output is correct
32 Correct 3200 ms 287228 KB Output is correct
33 Correct 2183 ms 285512 KB Output is correct
34 Correct 2339 ms 291224 KB Output is correct
35 Correct 2920 ms 290448 KB Output is correct
36 Correct 2199 ms 285984 KB Output is correct
37 Correct 2334 ms 291296 KB Output is correct
38 Correct 3095 ms 381156 KB Output is correct
39 Correct 3052 ms 381128 KB Output is correct
40 Correct 2933 ms 302352 KB Output is correct
41 Correct 3301 ms 465576 KB Output is correct
42 Correct 3818 ms 467608 KB Output is correct
43 Correct 3627 ms 467580 KB Output is correct
44 Correct 3534 ms 380828 KB Output is correct