Submission #547236

#	Time	Username	Problem	Language	Result	Execution time	Memory
547236		penguinhacker	Autobahn (COI21_autobahn)	C++14	100 / 100	97 ms	11200 KiB

autobahn

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

#define ll long long
#define ar array

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k, len;
	cin >> n >> k >> len;
	vector<ar<int, 2>> e;
	for (int i=0; i<n; ++i) {
		int l, t, r;
		cin >> l >> t >> r;
		e.push_back({l, 1});
		e.push_back({r+1, 2});
		if (l+t<=r) {
			e.push_back({l+t, 3});
			e.push_back({r+1, 4});
		}
	}
	sort(e.begin(), e.end());
	vector<ar<int, 3>> seg;
	int last=-1, all=0, ex=0;
	auto upd=[&](int t) {
		if (t==1||t==2)
			all+=t==1?1:-1;
		else
			ex+=t==3?1:-1;
	};
	for (int i=0; i<e.size(); ++i) {
		int x=e[i][0];
		if (all>=k&&ex)
			seg.push_back({last, x-1, ex});
		last=x;
		upd(e[i][1]);
		while(i+1<e.size()&&e[i+1][0]==x)
			upd(e[++i][1]);
	}
	if (seg.empty()) {
		cout << 0;
		return 0;
	}
	vector<ll> pre(seg.size()+1);
	for (int i=0; i<seg.size(); ++i)
		pre[i+1]=pre[i]+(ll)(seg[i][1]-seg[i][0]+1)*seg[i][2];
	ll ans=0;
	for (int i=0, j=0, x=seg[0][0]; ;) {
		while(j+1<seg.size()&&x+len-1>=seg[j+1][0])
			++j;
		if (i==j)
			ans=max(ans, (ll)(min(seg[i][1], x+len-1)-x+1)*seg[i][2]);
		else
			ans=max(ans, (pre[j]-pre[i+1])+(ll)(min(seg[j][1], x+len-1)-seg[j][0]+1)*seg[j][2]+(ll)(seg[i][1]-x+1)*seg[i][2]);
		if (x+len-1>=seg.back()[1])
			break;
		int nxt=(x+len-1>=seg[j][1]?seg[j+1][0]:seg[j][1])-len+1;
		if (nxt>seg[i][1]||seg[i+1][0]<=nxt) {
			++i;
			x=seg[i][0];
		} else
			x=nxt;
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i=0; i<e.size(); ++i) {
      |                ~^~~~~~~~~
autobahn.cpp:38:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   while(i+1<e.size()&&e[i+1][0]==x)
      |         ~~~^~~~~~~~~
autobahn.cpp:46:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i=0; i<seg.size(); ++i)
      |                ~^~~~~~~~~~~
autobahn.cpp:50:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   while(j+1<seg.size()&&x+len-1>=seg[j+1][0])
      |         ~~~^~~~~~~~~~~

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