oj.uz

Submission #79031

# Submission time Handle Problem Language Result Execution time Memory
79031 2018-10-10T17:24:58 Z gs14004 Meetings (IOI18_meetings) C++17
19 / 100
 5500 ms 28924 KB 
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 750005;
const int MAXT = 2100000;
const int inf = 1e9 + 10;

struct seg{
	int lim;
	pi tree[MAXT];
	void init(vector<int> &v){
		for(lim = 1; lim <= v.size(); lim <<= 1);
		fill(tree, tree + MAXT, pi(-1e9, 0));
		for(int i=0; i<v.size(); i++) tree[i + lim] = pi(v[i], i);
		for(int i=lim-1; i; i--) tree[i] = max(tree[2*i], tree[2*i+1]);
	}
	pi query(int s, int e){
		s += lim;
		e += lim;
		pi ret(-1e9, 0);
		while(s < e){
			if(s%2 == 1) ret = max(ret, tree[s++]);
			if(e%2 == 0) ret = max(ret, tree[e--]);
			s >>= 1;
			e >>= 1;
		}
		if(s == e) ret = max(ret, tree[s]);
		return ret;
	}
}seg;

struct node{
	int s, e, rep; // node range
	int lp, rp; // pointers
	int h; // height
}tr[MAXN];

int ptr, loc[MAXN], parL[MAXN], parR[MAXN];
lint dp[MAXN], lgo[MAXN], rgo[MAXN];
lint L_intercept[MAXN], R_intercept[MAXN];

void make_tree(int s, int e, int v){
	int h, m;
	tie(h, m) = seg.query(s, e);
	loc[m] = v;
	tr[v] = {s, e, m, -1, -1, h};
	if(s <= m - 1){
		ptr++;
		tr[v].lp = ptr;
		make_tree(s, m-1, tr[v].lp);
	}
	if(m + 1 <= e){
		ptr++;
		tr[v].rp = ptr;
		make_tree(m+1, e, tr[v].rp);
	}
}

lint go_left(int pos, int root){
	int L = pos;
	int v = loc[pos];
	root = loc[root];
	lint ret = 1e18;
	while(v != root){
		ret = min(ret, lgo[v] + 1ll * tr[v].h * (tr[v].e - L + 1));
		if(~tr[v].rp){
			ret = min(ret, lgo[v] + 1ll * tr[v].h * (tr[v].rep - L + 1) + dp[tr[v].rp]);
		}
		v = parL[v];
	}
	ret -= lgo[tr[root].lp];
//	printf("go_left %d -> %d = %lld\n", L, root, ret);
	return ret;
}

lint go_right(int pos, int root){
	int R = pos;
	int v = loc[pos];
	root = loc[root];
	lint ret = 1e18;
	while(v != root){
		ret = min(ret, rgo[v] + 1ll * tr[v].h * (R - tr[v].s + 1));
		if(~tr[v].lp){
			ret = min(ret, rgo[v] + 1ll * tr[v].h * (R - tr[v].rep + 1) + dp[tr[v].lp]);
		}
		v = parR[v];
	}
	ret -= rgo[tr[root].rp];
//	printf("go_right %d -> %d = %lld\n", R, root, ret);
	return ret;
}

vector<lint> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
	int n = H.size();
	int q = L.size();
	seg.init(H);
	make_tree(0, n-1, 0);
	for(int i=ptr; i>=0; i--){
		dp[i] = 1ll * H[tr[i].rep] * (tr[i].e - tr[i].s + 1);
		if(~tr[i].lp){
			dp[i] = min(dp[i], dp[tr[i].lp] + 1ll * H[tr[i].rep] * (tr[i].e - tr[i].rep + 1));
		}
		if(~tr[i].rp){
			dp[i] = min(dp[i], dp[tr[i].rp] + 1ll * H[tr[i].rep] * (tr[i].rep - tr[i].s + 1));
		}
	}
	for(int i=0; i<=ptr; i++){
		if(tr[i].s - 1 >= 0) parR[i] = loc[tr[i].s - 1];
		else parR[i] = -1;
		if(tr[i].e + 1 < n) parL[i] = loc[tr[i].e + 1];
		else parL[i] = -1;
		if(~tr[i].lp){
			lgo[tr[i].lp] = lgo[i] + 1ll * H[tr[i].rep] * (tr[i].e - tr[i].rep + 1);
			rgo[tr[i].lp] = rgo[i];
		}
		if(~tr[i].rp){
			lgo[tr[i].rp] = lgo[i];
			rgo[tr[i].rp] = rgo[i] + 1ll * H[tr[i].rep] * (tr[i].rep - tr[i].s + 1);
		}
	}
	vector<lint> ret(q);
	for(int i=0; i<q; i++){
		pi p = seg.query(L[i], R[i]);
		ret[i] = min({1ll * (R[i] - L[i] + 1) * p.first, 
			go_left(L[i], p.second) + 1ll * (R[i] - p.second + 1) * p.first, 
			go_right(R[i], p.second) + 1ll * (p.second - L[i] + 1) * p.first});
	}
	return ret;
}

Compilation message

meetings.cpp: In member function 'void seg::init(std::vector<int>&)':
meetings.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(lim = 1; lim <= v.size(); lim <<= 1);
                ~~~~^~~~~~~~~~~
meetings.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v.size(); i++) tree[i + lim] = pi(v[i], i);
                ~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16860 KB Output is correct
2 Correct 19 ms 16960 KB Output is correct
3 Correct 19 ms 17008 KB Output is correct
4 Correct 20 ms 16988 KB Output is correct
5 Correct 19 ms 16944 KB Output is correct
6 Correct 20 ms 17116 KB Output is correct
7 Correct 19 ms 16992 KB Output is correct
8 Correct 19 ms 17092 KB Output is correct
9 Correct 19 ms 17084 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16860 KB Output is correct
2 Correct 19 ms 16960 KB Output is correct
3 Correct 19 ms 17008 KB Output is correct
4 Correct 20 ms 16988 KB Output is correct
5 Correct 19 ms 16944 KB Output is correct
6 Correct 20 ms 17116 KB Output is correct
7 Correct 19 ms 16992 KB Output is correct
8 Correct 19 ms 17092 KB Output is correct
9 Correct 19 ms 17084 KB Output is correct
10 Correct 23 ms 17312 KB Output is correct
11 Correct 23 ms 17372 KB Output is correct
12 Correct 23 ms 17272 KB Output is correct
13 Correct 23 ms 17272 KB Output is correct
14 Correct 45 ms 17468 KB Output is correct
15 Correct 23 ms 17316 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16792 KB Output is correct
2 Correct 415 ms 18892 KB Output is correct
3 Execution timed out 5513 ms 28924 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16792 KB Output is correct
2 Correct 415 ms 18892 KB Output is correct
3 Execution timed out 5513 ms 28924 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16860 KB Output is correct
2 Correct 19 ms 16960 KB Output is correct
3 Correct 19 ms 17008 KB Output is correct
4 Correct 20 ms 16988 KB Output is correct
5 Correct 19 ms 16944 KB Output is correct
6 Correct 20 ms 17116 KB Output is correct
7 Correct 19 ms 16992 KB Output is correct
8 Correct 19 ms 17092 KB Output is correct
9 Correct 19 ms 17084 KB Output is correct
10 Correct 23 ms 17312 KB Output is correct
11 Correct 23 ms 17372 KB Output is correct
12 Correct 23 ms 17272 KB Output is correct
13 Correct 23 ms 17272 KB Output is correct
14 Correct 45 ms 17468 KB Output is correct
15 Correct 23 ms 17316 KB Output is correct
16 Correct 19 ms 16792 KB Output is correct
17 Correct 415 ms 18892 KB Output is correct
18 Execution timed out 5513 ms 28924 KB Time limit exceeded
19 Halted 0 ms 0 KB -