Submission #420524

#	Time	Username	Problem	Language	Result	Execution time	Memory
420524		MetalPower	Autobahn (COI21_autobahn)	C++14	100 / 100	268 ms	21880 KiB

autobahn

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

#define ll long long

// Observation #1 : We can use line sweep, using positions l, l + t, and r
	// positions l (cnt++)
	// positions l + t (debt++)
	// positions r (cnt--, debt--)

// Observation #2 : Happy Hour either starts at a position, or ends at a position
	// So there are a total of 9 * N positions

const int MX = 1e5 + 10;

int N, K, X, l[MX], r[MX], t[MX];
vector<int> v;

int cnt[9 * MX], dt[9 * MX]; ll pref[9 * MX];

void chmax(ll& a, ll b){
	if(b > a) a = b;
}

void add(int val){
	v.push_back(val);
	v.push_back(val - X);
	v.push_back(val + X);
}

inline int index(int val){
	vector<int>::iterator it = lower_bound(v.begin(), v.end(), val);
	if(it == v.end()) return -1;
	return (*it) == val ? (it - v.begin()) : -1;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

	cin >> N >> K >> X;

	for(int i = 0; i < N; i++){
		cin >> l[i] >> t[i] >> r[i];
		t[i] = min(l[i] + t[i], r[i] + 1);

		add(l[i]); add(t[i]); add(r[i] + 1);
	}

	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());

	int M = v.size();

	for(int i = 0; i < N; i++){
		int _l = index(l[i]), _t = index(t[i]), _r = index(r[i] + 1);
		cnt[_l]++; dt[_t]++; cnt[_r]--; dt[_r]--;
	}

	for(int i = 1; i < M; i++){
		cnt[i] += cnt[i - 1]; dt[i] += dt[i - 1];
	}

	for(int i = 1; i < M; i++){
		pref[i] = pref[i - 1] + 1ll * (v[i] - v[i - 1]) * (cnt[i - 1] >= K ? dt[i - 1] : 0);
	}

	ll ans = 0;

	for(int i = 0; i < M; i++){
		int nxt = index(v[i] + X);
		if(nxt != -1) chmax(ans, pref[nxt] - pref[i]);
	}

	cout << ans << '\n';
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50