Submission #420451

#	Time	Username	Problem	Language	Result	Execution time	Memory
420451		maximath_1	Autobahn (COI21_autobahn)	C++11	100 / 100	140 ms	7868 KiB

autobahn

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <random>
#include <deque>
using namespace std;

mt19937 rng(420691273);
#define ll long long
const int MX = 1e5 + 5;

int n, k, x;
struct dt{
	int l, m, r;
} arr[MX];

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n >> k >> x;
	vector<int> cc;
	for(int i = 0; i < n; i ++){
		cin >> arr[i].l >> arr[i].m >> arr[i].r;
		arr[i].r ++; arr[i].m += arr[i].l;
		cc.push_back(arr[i].l);
		cc.push_back(arr[i].m);
		cc.push_back(arr[i].r);
	}

	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());
	vector<int> cnt(cc.size() + 5, 0), ext(cc.size() + 5, 0);
	for(int i = 0; i < n; i ++){
		arr[i].l = lower_bound(cc.begin(), cc.end(), arr[i].l) - cc.begin();
		arr[i].m = lower_bound(cc.begin(), cc.end(), arr[i].m) - cc.begin();
		arr[i].r = lower_bound(cc.begin(), cc.end(), arr[i].r) - cc.begin();
		cnt[arr[i].l] ++; cnt[arr[i].r] --;
		ext[arr[i].m] ++; ext[arr[i].r] --;
	}
	for(int i = 1; i < cnt.size(); i ++){
		cnt[i] += cnt[i - 1];
		ext[i] += ext[i - 1];
	}

	ll ans = 0ll, res = 0ll;
	// begin
	for(int i = 0, j = -1; i < cc.size(); i ++){
		for(; j + 2 < cc.size() && cc[j + 2] - cc[i] < x;){
			j ++;
			if(cnt[j] >= k)
				res += (cc[j + 1] - cc[j]) * 1ll * ext[j];
		}
		ll tmp = 0ll;
		if(j + 1 < cc.size() && cnt[j + 1] >= k)
			tmp = (cc[i] + x - cc[j + 1]) * 1ll * ext[j + 1];
		if(ans < res + tmp)
			ans = res + tmp;
		if(cnt[i] >= k)
			res -= (cc[i + 1] - cc[i]) * 1ll * ext[i];
	}

	// end
	res = 0ll;
	for(int i = cc.size() - 1, j = cc.size() - 1; i >= 0; i --){
		if(cnt[i] >= k)
			res -= (cc[i + 1] - cc[i]) * 1ll * ext[i];
		for(; j > 0 && cc[i] - cc[j - 1] < x;){
			j --;
			if(cnt[j] >= k)
				res += (cc[j + 1] - cc[j]) * 1ll * ext[j];
		}
		ll tmp = 0ll;
		if(j > 0 && cnt[j - 1] >= k)
			tmp = (cc[j] - (cc[i] - x)) * 1ll * ext[j - 1];
		if(ans < res + tmp)
			ans = res + tmp;
	}

	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i = 1; i < cnt.size(); i ++){
      |                 ~~^~~~~~~~~~~~
autobahn.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i = 0, j = -1; i < cc.size(); i ++){
      |                         ~~^~~~~~~~~~~
autobahn.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(; j + 2 < cc.size() && cc[j + 2] - cc[i] < x;){
      |         ~~~~~~^~~~~~~~~~~
autobahn.cpp:57:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   if(j + 1 < cc.size() && cnt[j + 1] >= k)
      |      ~~~~~~^~~~~~~~~~~

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