Submission #436756

#	Time	Username	Problem	Language	Result	Execution time	Memory
436756		rqi	Meetings (IOI18_meetings)	C++14	41 / 100	1196 ms	161164 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;
typedef vector<ll> vl;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define bk back()
#define ins insert

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

const ll INF = 1e18;

void ckmax(int& a, int b){
	a = max(a, b);
}

void ckmin(ll& a, ll b){
	a = min(a, b);
}

const int MOD = 1e9+7;

const int mx = 100005;

mt19937 rng(127);

int N, Q;

struct Node{
	bool is_ID;
	array<ll, 21> meet_in_right;
	array<ll, 21> meet_in_left;
	array<ll, 21> meet_from_left;
	array<ll, 21> meet_from_right;
	int max_val;

	Node(){

	}

	Node(int val){
		if(val == -1){
			is_ID = 1;
		}
		else if(val == -2){ //use for comb
			is_ID = 0;
			for(int i = 1; i <= 20; i++){
				meet_in_right[i] = meet_in_left[i] = INF;
			}
		}
		else{
			is_ID = 0;
			max_val = val;
			for(int i = 1; i <= 20; i++){
				meet_in_right[i] = meet_in_left[i] = INF;
			}
			meet_in_right[val] = meet_in_left[val] = val;
			for(int i = 1; i <= 20; i++){
				meet_from_left[i] = meet_from_right[i] = max(i, val);
			}
		}
	}
};

void print(Node a){
	for(int i = 1; i <= 20; i++){
		cout << a.meet_in_right[i] << " " << a.meet_in_left[i] << "\n";
	}
}

Node comb(const Node& a, const Node& b){
	Node res = Node(-2);
	if(a.is_ID){
		res = b;
		return res;
	}
	if(b.is_ID){
		res = a;
		return res;
	}

	res.max_val = max(a.max_val, b.max_val);

	//compute res.meet_in_right
	
	for(int i = 1; i <= 20; i++){
		//consider left start
		ckmin(res.meet_in_right[max(i, b.max_val)], a.meet_in_right[i]+b.meet_from_left[i]);
		//consider right start
		ckmin(res.meet_in_right[i], a.meet_from_right[b.max_val]+b.meet_in_right[i]);
		ckmin(res.meet_in_right[b.max_val], a.meet_from_right[i]+b.meet_in_left[i]);
	}
	for(int i = 1; i <= 20; i++){
		//consider left start
		ckmin(res.meet_in_left[i], a.meet_in_left[i]+b.meet_from_left[a.max_val]);
		ckmin(res.meet_in_left[a.max_val], a.meet_in_right[i]+b.meet_from_left[i]);
		//consider right start
		ckmin(res.meet_in_left[max(a.max_val, i)], a.meet_from_right[i]+b.meet_in_left[i]);
	}

	for(int i = 1; i <= 20; i++){
		res.meet_from_left[i] = a.meet_from_left[i]+b.meet_from_left[max(i, a.max_val)];
		res.meet_from_right[i] = a.meet_from_right[max(i, b.max_val)]+b.meet_from_right[i];
	}
	

	return res;
}

const int SZ = 131072;
Node seg[2*SZ];

void pull(int ind){
	seg[ind] = comb(seg[2*ind], seg[2*ind+1]);
}

void build(){
	for(int i = SZ-1; i >= 1; i--){
		pull(i);
	}
}

Node query(int l, int r, int ind = 1, int L = 0, int R = SZ-1){
	if(r < L || R < l) return Node(-1);
	if(l <= L && R <= r){
		return seg[ind];
	}

	int M = (L+R)/2;
	return comb(query(l, r, 2*ind, L, M), query(l, r, 2*ind+1, M+1, R));
}

vl minimum_costs(vi H, vi L, vi R) {
	// cout << "HI" << "\n";
	// cout.flush();
	N = sz(H);
	Q = sz(L);

	for(int i = 0; i < N; i++){
		seg[SZ+i] = Node(H[i]);
	}
	build();

	// print(seg[SZ+0]);

	vl C(Q, INF);
	for(int i = 0; i < Q; i++){
		Node res = query(L[i], R[i]);
		for(int j = 1; j <= 20; j++){
			ckmin(C[i], res.meet_in_left[j]);
		}
	}	


	return C;
}

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