Submission #1049096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049096		Alihan_8	Meetings (IOI18_meetings)	C++17	60 / 100	5570 ms	120568 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const i64 inf = 1e15;

vector <int> h;

int n;

struct Info{
	i64 best;
	int l, r, x;
	
	Info *lf, *rg;
	
	Info(int l = 0, int r = -1) : best(0), l(l), r(r) {}
};

struct SegTree{
	Info *root = new Info();
	
	SegTree(){
		root = build(0, n - 1);
	}
	
	Info *build(int l, int r){
		Info *v = new Info(l, r);
		
		if ( l <= r ){
			int top = 0;
			
			for ( int i = l; i <= r; i++ ){
				chmax(top, h[i]);
			}
			
			vector <int> ids;
			
			for ( int i = l; i <= r; i++ ){
				if ( h[i] == top ) ids.pb(i);
			}
			
			v -> x = ids[(int)ids.size() / 2];
			
			Info *lf = build(l, v -> x - 1);
			Info *rg = build(v -> x + 1, r);
			
			v -> best = min(lf -> best + h[v -> x] * 1LL * (r - v -> x),
							rg -> best + h[v -> x] * 1LL * (v -> x - l)) + top;	
			v -> lf = lf;
			v -> rg = rg;
		}
		
		return v;
	}
	
	i64 qry(Info *v, int l, int r){
		if ( v -> l > v -> r ) return 0;
		
		if ( v -> x > r ) return qry(v -> lf, l, r);
		if ( v -> x < l ) return qry(v -> rg, l, r);
		
		if ( v -> l >= l && v -> r <= r ){
			return v -> best;
		}
		
		return min(qry(v -> lf, l, v -> x - 1) + h[v -> x] * 1LL * (r - v -> x + 1), 
				   qry(v -> rg, v -> x + 1, r) + h[v -> x] * 1LL * (v -> x - l + 1));
	}
	
	i64 qry(int l, int r){ return qry(root, l, r); } 
};
	
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	int q = L.size(); n = H.size(); h = H;
	
	// subtask #4
	
	SegTree seg;
	
	vector <i64> ans(q);
	
	for ( int i = 0; i < q; i++ ){
		ans[i] = seg.qry(L[i], R[i]);
	}
	
	return ans;
}

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