Submission #132902

#	Time	Username	Problem	Language	Result	Execution time	Memory
132902		KieranHorgan	Meetings (IOI18_meetings)	C++17	0 / 100	5532 ms	12508 KiB

meetings

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

const int MAXN = 100005;
int N, Q;
vector<int> H,L,R;


int ST[MAXN][20];
int lg(int 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];
			}
			if(H[ST[i][j-1]] < H[ST[i+(1<<(j-1))][j-1]]) {
				ST[i][j] = ST[i+(1<<(j-1))][j-1];
			}
			if(H[ST[i][j-1]] == H[ST[i+(1<<(j-1))][j-1]]) {
				if(rand()%2)
					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];
	}
	if(H[ST[i][j-1]] < H[ST[r+1-(1<<(j-1))][j-1]]) {
		return ST[r+1-(1<<(j-1))][j-1];
	}
	if(H[ST[i][j-1]] == H[ST[r+1-(1<<(j-1))][j-1]]) {
		if(rand()%2)
			return ST[i][j-1];
		else
			return ST[r+1-(1<<(j-1))][j-1];
	}
}

int solve(int l, int r) {
	if(l>r) return 0;
	int idx = query(l, r);
	int res = (r-l+1)*H[idx];
	res = min(res, (idx-l+1)*H[idx] + solve(idx+1, r));
	res = min(res, (r-idx+1)*H[idx] + solve(l, idx-1));
	return res;
}

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

	buildST();

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


	return C;
}

Compilation message (stderr)

meetings.cpp: In function 'int query(int, int)':
meetings.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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