Submission #79198

#	Time	Username	Problem	Language	Result	Execution time	Memory
79198		gs14004	Meetings (IOI18_meetings)	C++17	60 / 100	5623 ms	379788 KiB

meetings

#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 cht{
	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){
		lint ret = 1e18;
		for(auto &i : v) ret = min(ret, i.first * x + i.second);
		return ret;/*
		if(ptr == v.size()) return 1e18;
		while(ptr + 1 < v.size() && v[ptr].first * x + v[ptr].second > v[ptr+1].first * x + v[ptr+1].second){
			ptr++;
		}
		return v[ptr].first * x + v[ptr].second;
		*/
	}
}cht;

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));
					}
				}
			}
		}
		for(auto &i : rquery){
			for(int j=i.l; j<=i.r; j++){
				ret[i.idx] = min(ret[i.idx], 1ll * a[j] * i.x + b[j]);
			}
		}
		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 (stderr)

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 tree_cht::hld(int)':
meetings.cpp:126: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:158:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<query.size(); i++){
                ~^~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 40