Submission #1049073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049073		Alihan_8	Meetings (IOI18_meetings)	C++17	36 / 100	569 ms	786432 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, len;
	
	Info *lf, *rg;
	
	Info(int l = 0, int r = -1) : best(0), l(l), r(r), len(r - l + 1), lf(NULL), rg(NULL) {}
};

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 * rg -> len,
							rg -> best + h[v -> x] * 1LL * lf -> len) + top;	
			v -> lf = lf;
			v -> rg = rg;
		}
		
		return v;
	}
	
	Info *qry(Info *v, int l, int r){
		Info *ret = new Info();
		
		if ( v -> l > r || v -> r < l ) return ret;
		
		if ( v -> l >= l && v -> r <= r ){ 
			return v;
		}
		
		if ( !v -> lf ) return qry(v -> rg, l, r);
		if ( !v -> rg ) return qry(v -> lf, l, r);
		
		Info *lf = qry(v -> lf, l, r);
		Info *rg = qry(v -> rg, l, r);
		
		int cnt = (l <= v -> x && r >= v -> x);
		
		ret -> best = min(lf -> best + h[v -> x] * 1LL * rg -> len,
						  rg -> best + h[v -> x] * 1LL * lf -> len) + cnt * h[v -> x];
		ret -> len = lf -> len + rg -> len + cnt;
		
		return ret;
	}
	
	i64 qry(int l, int r){
		return qry(root, l, r) -> best;
	}
};
	
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: 0 / 24
• Subtask 5: 0 / 40