Submission #436423

#	Time	Username	Problem	Language	Result	Execution time	Memory
436423		rqi	Meetings (IOI18_meetings)	C++14	19 / 100	3259 ms	400368 KiB

meetings

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

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;
typedef vector<ll> vl;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define bk back()
#define ins insert

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

const ll INF = 1e18;

void ckmax(int& a, int b){
	a = max(a, b);
}

void ckmin(ll& a, ll b){
	a = min(a, b);
}

const int MOD = 1e9+7;

const int mx = 100005;

mt19937 rng(127);

int N, Q;

struct BIT{
	ll BT[5005];
	void upd(int pos, ll val){
		pos++;
		for(int i = pos; i < 5005; i+=i&-i){
			// cout << i << "\n";
			// cout.flush();
			BT[i]+=val;
		}
	}

	ll sum(int pos){
		ll res = 0;
		for(int i = pos; i > 0; i-=i&-i){
			// cout << i << "\n";
			// cout.flush();
			res+=BT[i];
		}
		return res;
	}

	ll query(int l, int r){
		l++;
		r++;
		return sum(r)-sum(l-1);
	}
};

BIT bt[5005];

vl minimum_costs(vi H, vi L, vi R) {
	// cout << "HI" << "\n";
	// cout.flush();
	N = sz(H);
	Q = sz(L);

	for(int i = 0; i < N; i++){
		bt[i].upd(i, H[i]);
		int cur_max = H[i];
		for(int j = i-1; j >= 0; j--){
			ckmax(cur_max, H[j]);
			bt[i].upd(j, cur_max);
		}
		cur_max = H[i];
		for(int j = i+1; j < N; j++){
			ckmax(cur_max, H[j]);
			bt[i].upd(j, cur_max);

			// cout << "building: " << i << " " << j << " " << cur_max << "\n";
		}
	}

	// for(int i = 0; i < N; i++){
	// 	for(int j = 0; j < N; j++){
	// 		cout << i << " " << j << " " << bt[i].query(j, j) << "\n";
	// 	}
	// }

	vl C(Q, INF);
	for(int i = 0; i < Q; i++){
		ll ans = INF;
		for(int j = L[i]; j <= R[i]; j++){
			ckmin(ans, bt[j].query(L[i], R[i]));
		}
		C[i] = ans;
	}
	return C;
}

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