Submission #132915

#	Time	Username	Problem	Language	Result	Execution time	Memory
132915		KieranHorgan	Meetings (IOI18_meetings)	C++17	19 / 100	5542 ms	281832 KiB

meetings

#pragma GCC optimize("Ofast")
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
// #define int long long
int N, Q;
vector<signed> H,L,R;


int ST[MAXN][20];
int lg(signed x) {return 31 - __builtin_clz(x);}
void buildST() {
	for(int i = 0; i < N; i++)
		ST[i][0] = i;
	for(int j = 1; j < 20; j++)
		for(int i = 0; i + (1<<j) <= N; i++) {
			if(H[ST[i][j-1]] > H[ST[i+(1<<(j-1))][j-1]])
				ST[i][j] = ST[i][j-1];
			else
				ST[i][j] = ST[i+(1<<(j-1))][j-1];
		}

}
int query(int l, int r) {
	int dif = (r-l+1);
	int j = lg(dif);
	j++;
	int i = l;
	if(H[ST[i][j-1]] > H[ST[r+1-(1<<(j-1))][j-1]])
		return ST[i][j-1];
	else
		return ST[r+1-(1<<(j-1))][j-1];
}

int sameLeft[MAXN];
int sameRight[MAXN];

unordered_map<long long, long long> dp;
long long shash(long long l, long long r) {
	return l*MAXN + r;
}

long long solve(long long l, long long r) {
	if(l>r) return 0;
	if(dp[shash(l,r)] != 0)
		return dp[shash(l,r)];
	long long idx = query(l, r);
	long long res = (r-l+1)*H[idx];
	long long midL = max((long long)sameLeft[idx], l);
	long long midR = min((long long)sameRight[idx], r);
	res = min(res, (midR-l+1)*H[idx] + solve(midR+1, r));
	res = min(res, (r-midL+1)*H[idx] + solve(l, midL-1));
	return dp[shash(l,r)] = res;
}

vector<long long> minimum_costs(vector<signed> H_, vector<signed> L_,
											    vector<signed> R_) {
	H=H_;L=L_;R=R_;
	Q = L.size();
	N = H.size();
	srand(time(NULL));

	buildST();

	sameLeft[0] = 0;
	for(int i = 1; i < N; i++) {
		if(H[i-1] == H[i])
			sameLeft[i] = sameLeft[i-1];
		else
			sameLeft[i] = i;
	}
	
	sameRight[N-1] = N-1;
	for(int i = N-1-1; i >= 0; i--) {
		if(H[i+1] == H[i])
			sameRight[i] = sameRight[i+1];
		else
			sameRight[i] = i;
	}

	vector<long long> C(Q);
	for(int i = 0; i < Q; i++) {
		C[i] = solve(L[i], R[i]);
	}

	return C;
}

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