oj.uz

Submission #250796

# Submission time Handle Problem Language Result Execution time Memory
250796 2020-07-19T07:37:42 Z oolimry Meetings (IOI18_meetings) C++14
100 / 100
 4127 ms 486244 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(line L){
		//push();
		if(get(L, m+1) < get(val, m+1)) swap(val, L);
		if(s == e) return;
		if(get(L,s) < get(val,s)) l->insert(L);
		else r->insert(L);
	}
	*/
	
	void findInsert(int S, int E, line L){
		if(s > E || S > e || S > E) return;
		push();
		
		if(S <= s && e <= E){
			if(get(val,s) > get(L,s)) swap(val, L);
			if(get(val,e) <= get(L,e)) return;
			if(s == e) return;
			
			if(get(val,m) <= get(L,m)) r->findInsert(S, E, L);
			else{
				swap(val, L);
				l->findInsert(S, E, L);
			}
		}
		l->findInsert(S, E, L);
		r->findInsert(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->findInsert(M, M, line(0,0));
	Right->findInsert(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->findInsert(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->findInsert(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 13 ms 17920 KB Output is correct
2 Correct 17 ms 18724 KB Output is correct
3 Correct 15 ms 18944 KB Output is correct
4 Correct 17 ms 18816 KB Output is correct
5 Correct 18 ms 18816 KB Output is correct
6 Correct 16 ms 19200 KB Output is correct
7 Correct 15 ms 18816 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 16 ms 19072 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17920 KB Output is correct
2 Correct 17 ms 18724 KB Output is correct
3 Correct 15 ms 18944 KB Output is correct
4 Correct 17 ms 18816 KB Output is correct
5 Correct 18 ms 18816 KB Output is correct
6 Correct 16 ms 19200 KB Output is correct
7 Correct 15 ms 18816 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 16 ms 19072 KB Output is correct
10 Correct 25 ms 19840 KB Output is correct
11 Correct 22 ms 19904 KB Output is correct
12 Correct 24 ms 19968 KB Output is correct
13 Correct 23 ms 19968 KB Output is correct
14 Correct 24 ms 20480 KB Output is correct
15 Correct 23 ms 19832 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17920 KB Output is correct
2 Correct 68 ms 24568 KB Output is correct
3 Correct 370 ms 66132 KB Output is correct
4 Correct 359 ms 54264 KB Output is correct
5 Correct 302 ms 65912 KB Output is correct
6 Correct 317 ms 67320 KB Output is correct
7 Correct 406 ms 71600 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17920 KB Output is correct
2 Correct 68 ms 24568 KB Output is correct
3 Correct 370 ms 66132 KB Output is correct
4 Correct 359 ms 54264 KB Output is correct
5 Correct 302 ms 65912 KB Output is correct
6 Correct 317 ms 67320 KB Output is correct
7 Correct 406 ms 71600 KB Output is correct
8 Correct 363 ms 55536 KB Output is correct
9 Correct 281 ms 56744 KB Output is correct
10 Correct 290 ms 57336 KB Output is correct
11 Correct 350 ms 55928 KB Output is correct
12 Correct 290 ms 55396 KB Output is correct
13 Correct 319 ms 56300 KB Output is correct
14 Correct 344 ms 68088 KB Output is correct
15 Correct 328 ms 55468 KB Output is correct
16 Correct 379 ms 68088 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17920 KB Output is correct
2 Correct 17 ms 18724 KB Output is correct
3 Correct 15 ms 18944 KB Output is correct
4 Correct 17 ms 18816 KB Output is correct
5 Correct 18 ms 18816 KB Output is correct
6 Correct 16 ms 19200 KB Output is correct
7 Correct 15 ms 18816 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 16 ms 19072 KB Output is correct
10 Correct 25 ms 19840 KB Output is correct
11 Correct 22 ms 19904 KB Output is correct
12 Correct 24 ms 19968 KB Output is correct
13 Correct 23 ms 19968 KB Output is correct
14 Correct 24 ms 20480 KB Output is correct
15 Correct 23 ms 19832 KB Output is correct
16 Correct 10 ms 17920 KB Output is correct
17 Correct 68 ms 24568 KB Output is correct
18 Correct 370 ms 66132 KB Output is correct
19 Correct 359 ms 54264 KB Output is correct
20 Correct 302 ms 65912 KB Output is correct
21 Correct 317 ms 67320 KB Output is correct
22 Correct 406 ms 71600 KB Output is correct
23 Correct 363 ms 55536 KB Output is correct
24 Correct 281 ms 56744 KB Output is correct
25 Correct 290 ms 57336 KB Output is correct
26 Correct 350 ms 55928 KB Output is correct
27 Correct 290 ms 55396 KB Output is correct
28 Correct 319 ms 56300 KB Output is correct
29 Correct 344 ms 68088 KB Output is correct
30 Correct 328 ms 55468 KB Output is correct
31 Correct 379 ms 68088 KB Output is correct
32 Correct 3406 ms 305856 KB Output is correct
33 Correct 2367 ms 304072 KB Output is correct
34 Correct 2459 ms 310028 KB Output is correct
35 Correct 3131 ms 309260 KB Output is correct
36 Correct 2253 ms 304656 KB Output is correct
37 Correct 2460 ms 310124 KB Output is correct
38 Correct 3400 ms 399944 KB Output is correct
39 Correct 3482 ms 399964 KB Output is correct
40 Correct 3330 ms 321112 KB Output is correct
41 Correct 3399 ms 484168 KB Output is correct
42 Correct 4127 ms 486244 KB Output is correct
43 Correct 3728 ms 486148 KB Output is correct
44 Correct 3729 ms 399428 KB Output is correct