oj.uz

Submission #250779

# Submission time Handle Problem Language Result Execution time Memory
250779 2020-07-19T06:32:41 Z oolimry Meetings (IOI18_meetings) C++14
17 / 100
 416 ms 70448 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){
		push();
		if(s == S && e == E) insert(L);
		else if(E <= m) l->findInsert(S,E,L);
		else if(S >= m+1) r->findInsert(S,E,L);
		else{
			l->findInsert(S,m,L);
			r->findInsert(m+1,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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17920 KB Output is correct
2 Incorrect 16 ms 18816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17920 KB Output is correct
2 Incorrect 16 ms 18816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17920 KB Output is correct
2 Correct 69 ms 24440 KB Output is correct
3 Correct 367 ms 65228 KB Output is correct
4 Correct 337 ms 54120 KB Output is correct
5 Correct 302 ms 65016 KB Output is correct
6 Correct 335 ms 66296 KB Output is correct
7 Correct 416 ms 70448 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17920 KB Output is correct
2 Correct 69 ms 24440 KB Output is correct
3 Correct 367 ms 65228 KB Output is correct
4 Correct 337 ms 54120 KB Output is correct
5 Correct 302 ms 65016 KB Output is correct
6 Correct 335 ms 66296 KB Output is correct
7 Correct 416 ms 70448 KB Output is correct
8 Incorrect 347 ms 55356 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17920 KB Output is correct
2 Incorrect 16 ms 18816 KB Output isn't correct
3 Halted 0 ms 0 KB -