oj.uz

Submission #79030

# Submission time Handle Problem Language Result Execution time Memory
79030 2018-10-10T17:11:40 Z gs14004 Meetings (IOI18_meetings) C++17
19 / 100
 5500 ms 28124 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], par[MAXN];
lint dp[MAXN], lgo[MAXN], rgo[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;
	lint ret = 1e18;
	while(pos != root){
		int v = loc[pos];
		ret = min(ret, lgo[v] - lgo[tr[loc[root]].lp] + 1ll * tr[v].h * (tr[v].e - L + 1));
		if(~tr[v].rp){
			ret = min(ret, lgo[v] - lgo[tr[loc[root]].lp] + 1ll * tr[v].h * (tr[v].rep - L + 1) + dp[tr[v].rp]);
		}
		pos = tr[v].e + 1;
	}
//	printf("go_left %d -> %d = %lld\n", L, root, ret);
	return ret;
}

lint go_right(int pos, int root){
	int R = pos;
	lint ret = 1e18;
	while(pos != root){
		int v = loc[pos];
		ret = min(ret, rgo[v] - rgo[tr[loc[root]].rp] + 1ll * tr[v].h * (R - tr[v].s + 1));
		if(~tr[v].lp){
			ret = min(ret, rgo[v] - rgo[tr[loc[root]].rp] + 1ll * tr[v].h * (R - tr[v].rep + 1) + dp[tr[v].lp]);
		}
		pos = tr[v].s - 1;
	}
//	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++){
//		printf("%d %d %d %d %d %d\n", i, tr[i].lp, tr[i].rp, tr[i].s, tr[i].e, tr[i].rep);
//		printf("LGO = %lld, RGO = %lld, DP = %lld\n", lgo[i], rgo[i], dp[i]);
		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 18 ms 16760 KB Output is correct
2 Correct 19 ms 16960 KB Output is correct
3 Correct 19 ms 16912 KB Output is correct
4 Correct 19 ms 17004 KB Output is correct
5 Correct 19 ms 16960 KB Output is correct
6 Correct 19 ms 17120 KB Output is correct
7 Correct 20 ms 16928 KB Output is correct
8 Correct 19 ms 17080 KB Output is correct
9 Correct 19 ms 16988 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16760 KB Output is correct
2 Correct 19 ms 16960 KB Output is correct
3 Correct 19 ms 16912 KB Output is correct
4 Correct 19 ms 17004 KB Output is correct
5 Correct 19 ms 16960 KB Output is correct
6 Correct 19 ms 17120 KB Output is correct
7 Correct 20 ms 16928 KB Output is correct
8 Correct 19 ms 17080 KB Output is correct
9 Correct 19 ms 16988 KB Output is correct
10 Correct 24 ms 17296 KB Output is correct
11 Correct 23 ms 17256 KB Output is correct
12 Correct 24 ms 17248 KB Output is correct
13 Correct 24 ms 17244 KB Output is correct
14 Correct 54 ms 17400 KB Output is correct
15 Correct 23 ms 17300 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16820 KB Output is correct
2 Correct 621 ms 18728 KB Output is correct
3 Execution timed out 5509 ms 28124 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 16820 KB Output is correct
2 Correct 621 ms 18728 KB Output is correct
3 Execution timed out 5509 ms 28124 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16760 KB Output is correct
2 Correct 19 ms 16960 KB Output is correct
3 Correct 19 ms 16912 KB Output is correct
4 Correct 19 ms 17004 KB Output is correct
5 Correct 19 ms 16960 KB Output is correct
6 Correct 19 ms 17120 KB Output is correct
7 Correct 20 ms 16928 KB Output is correct
8 Correct 19 ms 17080 KB Output is correct
9 Correct 19 ms 16988 KB Output is correct
10 Correct 24 ms 17296 KB Output is correct
11 Correct 23 ms 17256 KB Output is correct
12 Correct 24 ms 17248 KB Output is correct
13 Correct 24 ms 17244 KB Output is correct
14 Correct 54 ms 17400 KB Output is correct
15 Correct 23 ms 17300 KB Output is correct
16 Correct 19 ms 16820 KB Output is correct
17 Correct 621 ms 18728 KB Output is correct
18 Execution timed out 5509 ms 28124 KB Time limit exceeded
19 Halted 0 ms 0 KB -