Submission #1072592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072592		pawned	Meetings (IOI18_meetings)	C++17	17 / 100	104 ms	13352 KiB

meetings

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "meetings.h"

const int MAX = 750005;

struct Segtree {	// point upd, range max
	int sz;
	vi vals;
	Segtree(int N) {
		sz = 1;
		while (sz < N)
			sz *= 2;
		vals = vi(2 * sz, 0LL);
	}
	void upd(int pos, ll val, int id, int left, int right) {
		if (right - left == 1) {
			vals[id] = val;
			return;
		}
		int mid = (left + right) / 2;
		if (pos < mid)
			upd(pos, val, 2 * id + 1, left, mid);
		else
			upd(pos, val, 2 * id + 2, mid, right);
		vals[id] = max(vals[2 * id + 1], vals[2 * id + 2]);
	}
	void upd(int pos, ll val) {
		upd(pos, val, 0, 0, sz);
	}
	ll query(int qleft, int qright, int id, int left, int right) {
		if (qleft <= left && right <= qright)
			return vals[id];
		if (qright <= left || right <= qleft)
			return 0;
		int mid = (left + right) / 2;
		ll s1 = query(qleft, qright, 2 * id + 1, left, mid);
		ll s2 = query(qleft, qright, 2 * id + 2, mid, right);
		return max(s1, s2);
	}
	ll query(int qleft, int qright) {
		return query(qleft, qright, 0, 0, sz);
	}
};

vi minimum_costs(vector<int> H_g, vector<int> L_g, vector<int> R_g) {
	int N = H_g.size();
	vi H(N);
	for (int i = 0; i < N; i++) {
		H[i] = H_g[i];
	}
	int Q = L_g.size();
	vector<ii> queries;
	for (int i = 0; i < Q; i++) {
		queries.pb({L_g[i], R_g[i]});
	}
	vi maxl(N, 0);
	int curr = 1;
	for (int i = 0; i < N; i++) {
		if (H[i] == 2) {
			maxl[i] = 0;
			curr = 1;
		}
		else {
			maxl[i] = curr;
			curr++;
		}
	}
	for (int i = N - 2; i >= 0; i--) {
		if (maxl[i] != 0)
			maxl[i] = max(maxl[i], maxl[i + 1]);
	}
/*	cout<<"maxl: ";
	for (int x : maxl)
		cout<<x<<" ";
	cout<<endl;*/
	Segtree st(N);
	for (int i = 0; i < N; i++) {
		st.upd(i, maxl[i]);
	}
	set<int> all2;
	for (int i = 0; i < N; i++) {
		if (H[i] == 2)
			all2.insert(i);
	}
	vi ans(Q, -1);
	for (int i = 0; i < Q; i++) {
//		cout<<"at "<<i<<endl;
		int L = queries[i].fi;
		int R = queries[i].se;
//		cout<<"L, R: "<<L<<" "<<R<<endl;
		auto it = all2.lower_bound(L);
		if (it == all2.end() || (*it) > R) {	// no bad
			ans[i] = R - L + 1;
			continue;
		}
		auto it2 = --all2.lower_bound(R + 1);
		int p1 = *it;
		int p2 = *it2;
//		cout<<"p1, p2: "<<p1<<" "<<p2<<endl;
		ll maxc = max(p1 - L, R - p2);
		maxc = max(maxc, st.query(p1, p2 + 1));
//		cout<<"maxc: "<<maxc<<endl;
		ans[i] = 2 * (R - L + 1) - maxc;
	}
	return ans;
}

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