제출 #1048972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1048972		Alihan_8	모임들 (IOI18_meetings)	C++17	0 / 100	852 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;

const int N = 1e5 + 1;

int n;

struct SegTree{
	struct Info{
		i64 dp[21][21], le[21], ri[21];
		int mx;
		
		Info(){
			for ( int i = 0; i <= 20; i++ ){
				for ( int j = 0; j <= 20; j++ ){
					dp[i][j] = inf;
				}
			}
 			
 			for ( int h = 0; h <= 20; h++ ){
				le[h] = ri[h] = inf;
			} mx = -1;
		}
	};
	
	vector <Info> T;
	
	void modify(int n){ T.resize(n * 4 + 5); }
		
	void merge(Info &rt, const Info &lf, const Info &rg){
		rt = Info();
		
		for ( int x = 0; x <= 20; x++ ){
			for ( int y = 0; y <= 20; y++ ){
				chmin(rt.dp[x][max(rg.mx, y)], lf.dp[x][y] + rg.le[y]);
				chmin(rt.dp[max(x, lf.mx)][y], rg.dp[x][y] + lf.ri[x]);
			}
		}
		
		for ( int h = 0; h <= 20; h++ ){
			rt.le[h] = lf.le[h] + rg.le[max(lf.mx, h)];
			rt.ri[h] = rg.ri[h] + lf.ri[max(rg.mx, h)];
		}
		
		rt.mx = max(lf.mx, rg.mx);
	}
	
	void upd(int v, int l, int r, int p, int x){
		if ( l == r ){
			T[v].dp[x][x] = x;
			T[v].mx = x;
			
			for ( int h = 0; h <= 20; h++ ){
				T[v].le[h] = max(h, x);
				T[v].ri[h] = max(h, x);
			}
			
			return;
		}
		
		int m = (l + r) / 2;
		
		if ( p <= m ) upd(v * 2, l, m, p, x);
		else  upd(v * 2 + 1, m + 1, r, p, x);
		
		merge(T[v], T[v * 2], T[v * 2 + 1]);
	}
	
	void upd(int p, int x){ upd(1, 0, n - 1, p, x); }	
	
	Info get(int v, int l, int r, int tl, int tr){
		Info ret;
		
		if ( l > tr or r < tl ) return ret;
		
		if ( tl <= l && tr >= r ){
			return T[v];
		}
		
		int m = (l + r) / 2;
		
		if ( m < tl ) return get(v * 2 + 1, m + 1, r, tl, tr);
		
		if ( m + 1 > tr ) return get(v * 2, l, m, tl, tr);
		
		merge(ret, get(v * 2, l, m, tl, tr), get(v * 2 + 1, m + 1, r, tl, tr));
		
		return ret;
	} 
	
	i64 qry(int l, int r){
		Info q = get(1, 0, n - 1, l, r);
		
		i64 opt = inf;
		
		for ( int x = 0; x <= 20; x++ ){
			for ( int y = 0; y <= 20; y++ ){
				chmin(opt, q.dp[x][y]);
			}
		}
		
		return opt;
	};
} seg;

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(); 
	
	// subtask #4
	
	seg.modify(n);
	
	for ( int i = 0; i < n; i++ ){
		seg.upd(i, H[i]);
	}
	
	vector <i64> ans(q);
	
	for ( int i = 0; i < q; i++ ){
		ans[i] = seg.qry(L[i], R[i]);
	}
	
	return ans;
}

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