Submission #420413

#	Time	Username	Problem	Language	Result	Execution time	Memory
420413		Berted	Autobahn (COI21_autobahn)	C++14	100 / 100	124 ms	7340 KiB

autobahn

#include <iostream>
#include <vector>
#include <algorithm>

#define ll long long
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

const int INF = 1e9 + 7;

int N, K, X;
int cur[2];

vector<int> C;
vector<pii> op;
int val[300005];

ll ret = 0;

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0);
	cin >> N >> K >> X;

	C.push_back(-INF); C.push_back(INF);
	for (int i = 0; i < N; i++)
	{
		int L, t, R; cin >> L >> t >> R; L--;
		C.push_back(L); C.push_back(R);
		op.push_back({L, 1});
		op.push_back({R, -1});

		if (L + t < R)
		{
			C.push_back(L + t);
			op.push_back({L + t, 2});
			op.push_back({R, -2});
		}
	}

	sort(C.begin(), C.end());
	C.resize(unique(C.begin(), C.end()) - C.begin());
	sort(op.begin(), op.end());

	int j = 0;
	for (int i = 0; i < C.size(); i++)
	{
		for (; j < op.size() && op[j].fst <= C[i]; j++)
		{
			if (op[j].snd < 0) {cur[-op[j].snd - 1]--;}
			else {cur[op[j].snd - 1]++;}
		}
		if (cur[0] >= K) val[i] = cur[1];
		//cerr << i << ": " << C[i] << " " << cur[0] << " " << cur[1] << "\n";
	}

	j = 0; ll tmp = 0;
	for (int i = 1; i < C.size(); i++)
	{
		while (j < i - 1 && C[i] - C[j] > X)
		{
			ret = max(ret, (ll)(X - C[i - 1] + C[j]) * val[i - 1] + tmp);
			tmp -= (ll)(C[j + 1] - C[j]) * val[j]; j++;
		}
		if (C[i] - C[i - 1] <= X) tmp += (ll)(C[i] - C[i - 1]) * val[i - 1];
		else j++;
		if (j) ret = max(ret, tmp + (ll)(X - C[i] + C[j]) * val[j - 1]);
		else ret = max(ret, tmp);
	}

	cout << ret << "\n";

	return 0;
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i = 0; i < C.size(); i++)
      |                  ~~^~~~~~~~~~
autobahn.cpp:51:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (; j < op.size() && op[j].fst <= C[i]; j++)
      |          ~~^~~~~~~~~~~
autobahn.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 1; i < C.size(); i++)
      |                  ~~^~~~~~~~~~

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