Submission #250883

#	Time	Username	Problem	Language	Result	Execution time	Memory
250883		oolimry	Meetings (IOI18_meetings)	C++14	100 / 100	3818 ms	467608 KiB

meetings

#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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40