oj.uz

Submission #79203

# Submission time Handle Problem Language Result Execution time Memory
79203 2018-10-11T16:03:56 Z gs14004 Meetings (IOI18_meetings) C++17
60 / 100
 5500 ms 600480 KB 
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using lint = long long;
using pi = pair<int, int>;
using line = pair<lint, lint>;
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(-inf, 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(-inf, 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);
	}
}

struct chtt{
	vector<line> v;
	int ptr;
	void clear(){
		ptr = 0;
		v.clear();
	}
	bool bad(line a, line b, line c){
		long double insecab = (long double)(b.second - a.second) / (a.first - b.first);
		long double insecbc = (long double)(c.second - b.second) / (b.first - c.first);
		return insecab >= insecbc;
	}
	void add(int x, lint y){
		if(v.size() > ptr && v.back().first == x){
			if(v.back().second <= y) return;
			else v.pop_back();
		}
		while(v.size() >= ptr + 2 && bad(v[v.size()-2], v.back(), line(x, y))){
			v.pop_back();
		}
		v.emplace_back(x, y);
	}
	lint query(int x){
		if(ptr == v.size()) return 1e18;
		int s = 0, e = v.size() - 1;
		while(s != e){
			int m= (s+e)/2;
			if(v[m].first * x + v[m].second > v[m+1].first * x + v[m+1].second){
				s = m+1;
			}
			else e = m;
		}
		return v[s].first * x + v[s].second;
	}
}cht;


struct segtree{
	chtt tree[MAXT];
	int lim;
	void init(int n, int *a, lint *b){
		for(lim = 1; lim <= n; lim <<= 1);
		for(int i=0; i<2*lim; i++) tree[i].clear();
		for(int i=1; i<=n; i++){
			for(int j=i+lim; j; j>>=1) tree[j].add(a[i], b[i]);
		}
	}
	lint query(int s, int e, int x){
		s += lim;
		e += lim;
		lint ret = 1e18;
		while(s < e){
			if(s%2 == 1) ret = min(ret, tree[s++].query(x));
			if(e%2 == 0) ret = min(ret, tree[e--].query(x));
			s >>= 1;
			e >>= 1;
		}
		if(s == e) ret = min(ret, tree[s].query(x));
		return ret;
	}
}chtseg;

struct tree_cht{
	struct queries{
		int s, e, x, idx;
		bool operator<(const queries &b)const{
			return x < b.x;
		}
	};
	struct range_query{
		int l, r, x, idx;
	};
	int n, par[MAXN];
	int a[MAXN]; lint b[MAXN];
	vector<int> gph[MAXN];
	vector<queries> query;
	int sz[MAXN], dfn[MAXN], chn[MAXN], cnt[MAXN], piv;
	void dfs(int x){
		sz[x] = 1;
		for(auto &i : gph[x]){
			dfs(i);
			sz[x] += sz[i];
		}
	}
	void hld(int x){
		dfn[x] = ++piv;
		cnt[chn[x]]++;
		if(gph[x].empty()) return;
		chn[gph[x][0]] = chn[x];
		hld(gph[x][0]);
		for(int i=1; i<gph[x].size(); i++){
			chn[gph[x][i]] = gph[x][i];
			hld(gph[x][i]);
		}
	}
	void build(int _n, int *p, node *t, lint *intercept){
		a[0] = inf;
		n = _n + 1;
		for(int i=1; i<n; i++){
			par[i] = p[i-1] + 1;
			gph[par[i]].push_back(i);
		}
		dfs(0);
		for(int i=0; i<n; i++){
			sort(gph[i].begin(), gph[i].end(), [&](const int &a, const int &b){
				return sz[a] > sz[b];
			});
		}
		hld(0);
		for(int i=1; i<n; i++){
			a[dfn[i]] = t[i-1].h;
			b[dfn[i]] = intercept[i-1];
		}
	}
	void add_query(int s, int e, int x){
		query.push_back({s + 1, e + 1, x, (int)query.size()});
	}
	vector<pi> prefix_query[MAXN];
	vector<range_query> rquery;
	vector<lint> batch(){
		vector<lint> ret(query.size(), 1e18);
		sort(query.begin(), query.end());
		for(int i=0; i<query.size(); i++){
			int pos = query[i].s;
			while(chn[pos] != chn[query[i].e]){
				prefix_query[dfn[pos]].push_back(pi(query[i].x, query[i].idx));
				pos = par[chn[pos]];
			}
			if(dfn[query[i].e] < dfn[pos]){
				rquery.push_back({dfn[query[i].e] + 1, dfn[pos], query[i].x, query[i].idx});
			}
		}
		for(int i=0; i<n; i++){
			if(chn[i] == i){
				cht.clear();
				for(int j=dfn[i]; j<dfn[i]+cnt[i]; j++){
					cht.add(a[j], b[j]);
					for(auto &k : prefix_query[j]){
						ret[k.second] = min(ret[k.second], cht.query(k.first));
					}
				}
			}
		}
		chtseg.init(n, a, b);
		for(auto &i : rquery){
			ret[i.idx] = min(ret[i.idx], chtseg.query(i.l, i.r, i.x));
		}
		return ret;
	}
}t1, t2;

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);
		}
		L_intercept[i] = lgo[i] + 1ll * tr[i].h * (tr[i].e + 1);
		if(~tr[i].rp){
			L_intercept[i] = min(L_intercept[i], lgo[i] + 1ll * tr[i].h * (tr[i].rep + 1) + dp[tr[i].rp]);
		}
		R_intercept[i] = rgo[i] + 1ll * tr[i].h * (1 - tr[i].s);
		if(~tr[i].lp){
			R_intercept[i] = min(R_intercept[i], rgo[i] + 1ll * tr[i].h * (1 - tr[i].rep) + dp[tr[i].lp]);
		}
	}
	t1.build(ptr + 1, parL, tr, L_intercept);
	t2.build(ptr + 1, parR, tr, R_intercept);
	vector<pi> lca(q);
	for(int i=0; i<q; i++){
		lca[i] = seg.query(L[i], R[i]);
		t1.add_query(loc[L[i]], loc[lca[i].second], -L[i]);
		t2.add_query(loc[R[i]], loc[lca[i].second], R[i]);
	}
	auto sol1 = t1.batch();
	auto sol2 = t2.batch();
	vector<lint> ret(q);
	for(int i=0; i<q; i++){
		pi p = lca[i];
		int root_num = loc[p.second]; 
		ret[i] = 1ll * (R[i] - L[i] + 1) * p.first;
		if(L[i] < p.second){
			ret[i] = min(ret[i], sol1[i] + 1ll * (R[i] - p.second + 1) * p.first - lgo[tr[root_num].lp]);
		}
		if(p.second < R[i]){
			ret[i] = min(ret[i], sol2[i] + 1ll * (p.second - L[i] + 1) * p.first - rgo[tr[root_num].rp]);
		}
	}
	return ret;
}

Compilation message

meetings.cpp: In member function 'void seg::init(std::vector<int>&)':
meetings.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(lim = 1; lim <= v.size(); lim <<= 1);
                ~~~~^~~~~~~~~~~
meetings.cpp:17: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);
                ~^~~~~~~~~
meetings.cpp: In member function 'void chtt::add(int, lint)':
meetings.cpp:75:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(v.size() > ptr && v.back().first == x){
      ~~~~~~~~~^~~~~
meetings.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(v.size() >= ptr + 2 && bad(v[v.size()-2], v.back(), line(x, y))){
         ~~~~~~~~~^~~~~~~~~~
meetings.cpp: In member function 'lint chtt::query(int)':
meetings.cpp:85:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ptr == v.size()) return 1e18;
      ~~~~^~~~~~~~~~~
meetings.cpp: In member function 'void tree_cht::hld(int)':
meetings.cpp:152:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<gph[x].size(); i++){
                ~^~~~~~~~~~~~~~
meetings.cpp: In member function 'std::vector<long long int> tree_cht::batch()':
meetings.cpp:184:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<query.size(); i++){
                ~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 153072 KB Output is correct
2 Correct 147 ms 153964 KB Output is correct
3 Correct 146 ms 153940 KB Output is correct
4 Correct 146 ms 154004 KB Output is correct
5 Correct 144 ms 154036 KB Output is correct
6 Correct 153 ms 154320 KB Output is correct
7 Correct 146 ms 153964 KB Output is correct
8 Correct 143 ms 154096 KB Output is correct
9 Correct 144 ms 153956 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 153072 KB Output is correct
2 Correct 147 ms 153964 KB Output is correct
3 Correct 146 ms 153940 KB Output is correct
4 Correct 146 ms 154004 KB Output is correct
5 Correct 144 ms 154036 KB Output is correct
6 Correct 153 ms 154320 KB Output is correct
7 Correct 146 ms 153964 KB Output is correct
8 Correct 143 ms 154096 KB Output is correct
9 Correct 144 ms 153956 KB Output is correct
10 Correct 156 ms 155512 KB Output is correct
11 Correct 155 ms 155608 KB Output is correct
12 Correct 161 ms 155612 KB Output is correct
13 Correct 156 ms 155512 KB Output is correct
14 Correct 171 ms 156180 KB Output is correct
15 Correct 168 ms 155484 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 153072 KB Output is correct
2 Correct 215 ms 161216 KB Output is correct
3 Correct 604 ms 200020 KB Output is correct
4 Correct 358 ms 191160 KB Output is correct
5 Correct 548 ms 196572 KB Output is correct
6 Correct 338 ms 192348 KB Output is correct
7 Correct 371 ms 193860 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 153072 KB Output is correct
2 Correct 215 ms 161216 KB Output is correct
3 Correct 604 ms 200020 KB Output is correct
4 Correct 358 ms 191160 KB Output is correct
5 Correct 548 ms 196572 KB Output is correct
6 Correct 338 ms 192348 KB Output is correct
7 Correct 371 ms 193860 KB Output is correct
8 Correct 711 ms 197648 KB Output is correct
9 Correct 594 ms 195104 KB Output is correct
10 Correct 648 ms 198592 KB Output is correct
11 Correct 633 ms 200228 KB Output is correct
12 Correct 566 ms 197332 KB Output is correct
13 Correct 615 ms 200660 KB Output is correct
14 Correct 827 ms 215788 KB Output is correct
15 Correct 683 ms 200668 KB Output is correct
16 Correct 372 ms 195664 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 153072 KB Output is correct
2 Correct 147 ms 153964 KB Output is correct
3 Correct 146 ms 153940 KB Output is correct
4 Correct 146 ms 154004 KB Output is correct
5 Correct 144 ms 154036 KB Output is correct
6 Correct 153 ms 154320 KB Output is correct
7 Correct 146 ms 153964 KB Output is correct
8 Correct 143 ms 154096 KB Output is correct
9 Correct 144 ms 153956 KB Output is correct
10 Correct 156 ms 155512 KB Output is correct
11 Correct 155 ms 155608 KB Output is correct
12 Correct 161 ms 155612 KB Output is correct
13 Correct 156 ms 155512 KB Output is correct
14 Correct 171 ms 156180 KB Output is correct
15 Correct 168 ms 155484 KB Output is correct
16 Correct 175 ms 153072 KB Output is correct
17 Correct 215 ms 161216 KB Output is correct
18 Correct 604 ms 200020 KB Output is correct
19 Correct 358 ms 191160 KB Output is correct
20 Correct 548 ms 196572 KB Output is correct
21 Correct 338 ms 192348 KB Output is correct
22 Correct 371 ms 193860 KB Output is correct
23 Correct 711 ms 197648 KB Output is correct
24 Correct 594 ms 195104 KB Output is correct
25 Correct 648 ms 198592 KB Output is correct
26 Correct 633 ms 200228 KB Output is correct
27 Correct 566 ms 197332 KB Output is correct
28 Correct 615 ms 200660 KB Output is correct
29 Correct 827 ms 215788 KB Output is correct
30 Correct 683 ms 200668 KB Output is correct
31 Correct 372 ms 195664 KB Output is correct
32 Correct 3184 ms 521324 KB Output is correct
33 Correct 2764 ms 508636 KB Output is correct
34 Correct 2963 ms 502256 KB Output is correct
35 Correct 4374 ms 499528 KB Output is correct
36 Correct 3745 ms 475936 KB Output is correct
37 Correct 4058 ms 502824 KB Output is correct
38 Execution timed out 5606 ms 600480 KB Time limit exceeded
39 Halted 0 ms 0 KB -