제출 #765887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765887		ono_de206	모임들 (IOI18_meetings)	C++14	0 / 100	419 ms	786432 KiB

meetings

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

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int mxn = 1e5 + 10, maxVal = 20;
const long long inf = 1e18;
int h[mxn];

struct node {
	long long dp[maxVal + 1][maxVal + 1];
	pair<long long, int> l[maxVal + 1], r[maxVal + 1];
	node() {
		for(int i = 1; i <= maxVal; i++) {
			for(int j = 1; j <= maxVal; j++) {
				dp[i][j] = -1;
			}
			l[i] = r[i] = {-1, -1};
		}
	}
} d[mxn * 4];

void mnn(long long& a, long long b) {
	if(a == -1 || a > b) a = b;
}

node operator+(const node& a, const node& b) {
	node ret;
	for(int i = 1; i <= maxVal; i++) {
		for(int j = 1; j <= maxVal; j++) {
			if(~a.dp[i][j]) {
				mnn(ret.dp[i][b.l[j].ss], a.dp[i][j] + b.l[j].ff);
			}
			if(~b.dp[i][j]) {
				mnn(ret.dp[a.r[i].ss][j], b.dp[i][j] + a.r[i].ff);
			}
		}
		ret.l[i] = {a.l[i].ff + b.l[a.l[i].ss].ff, b.l[a.l[i].ss].ss};
		ret.r[i] = {b.r[i].ff + a.r[b.r[i].ss].ff, a.r[b.r[i].ss].ss};
	}
	return ret;
}

void build(int l, int r, int i) {
	if(l == r) {
		d[i].dp[h[l]][h[l]] = h[l];
		for(int j = 1; j <= maxVal; j++) {
			d[i].l[j] = d[i].r[j] = {max(j, h[l]), max(j, h[l])};
		}
		return;
	}
	int m = (l + r) / 2;
	build(l, m, i * 2);
	build(m + 1, r, i * 2 + 1);
	d[i] = d[i * 2] + d[i * 2 + 1];
}

node query(int l, int r, int i, int x, int y) {
	if(l >= x && r <= y) return d[i];
	int m = (l + r) / 2;
	if(y <= m) return query(l, m, i * 2 , x, y);
	if(x > m) return query(m + 1, r, i * 2 + 1, x, y);
	return query(l, m, i * 2, x, y) + query(m + 1, r, i * 2 + 1, x, y); 
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	int Q = L.size(), n = H.size();
	vector<long long> ret(Q);

	for(int i = 1; i <= n; i++) {
		h[i] = H[i - 1];
	}
	build(1, n, 1);
	for(int i = 0; i < Q; i++) {
		int l = L[i] + 1, r = R[i] + 1;
		node qu = query(1, n, 1, l, r);
		ret[i] = inf;
		for(int j = 1; j <= maxVal; j++) {
			for(int k = 1; k <= maxVal; k++) {
				if(~qu.dp[j][k]) ret[i] = min(ret[i], qu.dp[j][k]);
			}
		}
	}
	return ret;
}

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