oj.uz

답안 #250812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250812 2020-07-19T08:15:20 Z oolimry 모임들 (IOI18_meetings) C++14
100 / 100
 3905 ms 486072 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
		}
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17920 KB Output is correct
2 Correct 15 ms 18816 KB Output is correct
3 Correct 15 ms 18816 KB Output is correct
4 Correct 16 ms 18816 KB Output is correct
5 Correct 16 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 17 ms 19072 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17920 KB Output is correct
2 Correct 15 ms 18816 KB Output is correct
3 Correct 15 ms 18816 KB Output is correct
4 Correct 16 ms 18816 KB Output is correct
5 Correct 16 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 17 ms 19072 KB Output is correct
10 Correct 24 ms 19712 KB Output is correct
11 Correct 23 ms 19776 KB Output is correct
12 Correct 23 ms 19840 KB Output is correct
13 Correct 22 ms 19840 KB Output is correct
14 Correct 24 ms 20352 KB Output is correct
15 Correct 23 ms 19840 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 17920 KB Output is correct
2 Correct 72 ms 24568 KB Output is correct
3 Correct 348 ms 67960 KB Output is correct
4 Correct 339 ms 56312 KB Output is correct
5 Correct 295 ms 67704 KB Output is correct
6 Correct 322 ms 69240 KB Output is correct
7 Correct 381 ms 73648 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 17920 KB Output is correct
2 Correct 72 ms 24568 KB Output is correct
3 Correct 348 ms 67960 KB Output is correct
4 Correct 339 ms 56312 KB Output is correct
5 Correct 295 ms 67704 KB Output is correct
6 Correct 322 ms 69240 KB Output is correct
7 Correct 381 ms 73648 KB Output is correct
8 Correct 393 ms 57496 KB Output is correct
9 Correct 295 ms 56620 KB Output is correct
10 Correct 303 ms 57592 KB Output is correct
11 Correct 330 ms 56072 KB Output is correct
12 Correct 288 ms 55396 KB Output is correct
13 Correct 294 ms 56312 KB Output is correct
14 Correct 380 ms 67960 KB Output is correct
15 Correct 329 ms 55596 KB Output is correct
16 Correct 376 ms 68232 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17920 KB Output is correct
2 Correct 15 ms 18816 KB Output is correct
3 Correct 15 ms 18816 KB Output is correct
4 Correct 16 ms 18816 KB Output is correct
5 Correct 16 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 17 ms 19072 KB Output is correct
10 Correct 24 ms 19712 KB Output is correct
11 Correct 23 ms 19776 KB Output is correct
12 Correct 23 ms 19840 KB Output is correct
13 Correct 22 ms 19840 KB Output is correct
14 Correct 24 ms 20352 KB Output is correct
15 Correct 23 ms 19840 KB Output is correct
16 Correct 12 ms 17920 KB Output is correct
17 Correct 72 ms 24568 KB Output is correct
18 Correct 348 ms 67960 KB Output is correct
19 Correct 339 ms 56312 KB Output is correct
20 Correct 295 ms 67704 KB Output is correct
21 Correct 322 ms 69240 KB Output is correct
22 Correct 381 ms 73648 KB Output is correct
23 Correct 393 ms 57496 KB Output is correct
24 Correct 295 ms 56620 KB Output is correct
25 Correct 303 ms 57592 KB Output is correct
26 Correct 330 ms 56072 KB Output is correct
27 Correct 288 ms 55396 KB Output is correct
28 Correct 294 ms 56312 KB Output is correct
29 Correct 380 ms 67960 KB Output is correct
30 Correct 329 ms 55596 KB Output is correct
31 Correct 376 ms 68232 KB Output is correct
32 Correct 3255 ms 305908 KB Output is correct
33 Correct 2263 ms 304140 KB Output is correct
34 Correct 2407 ms 309944 KB Output is correct
35 Correct 2969 ms 309160 KB Output is correct
36 Correct 2273 ms 304572 KB Output is correct
37 Correct 2406 ms 309992 KB Output is correct
38 Correct 3157 ms 399932 KB Output is correct
39 Correct 3324 ms 399860 KB Output is correct
40 Correct 3026 ms 321100 KB Output is correct
41 Correct 3584 ms 484288 KB Output is correct
42 Correct 3905 ms 486072 KB Output is correct
43 Correct 3808 ms 485988 KB Output is correct
44 Correct 3529 ms 399392 KB Output is correct