Submission #462023

#	Time	Username	Problem	Language	Result	Execution time	Memory
462023		Jasiekstrz	Autobahn (COI21_autobahn)	C++17	100 / 100	89 ms	6604 KiB

autobahn

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
vector<pair<int,int>> ev;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,k,x;
	cin>>n>>k>>x;
	for(int i=1;i<=n;i++)
	{
		int l,r,t;
		cin>>l>>t>>r;
		if(l+t<=r)
		{
			ev.emplace_back(l+t,0);
			ev.emplace_back(r+1,1);
		}
		ev.emplace_back(l,2);
		ev.emplace_back(r+1,3);
	}
	sort(ev.begin(),ev.end());
	int l=-x,r=0;
	int cntl=0,cntr=0;
	int opl=0,opr=0;
	long long ans=0,tmp=0;
	for(int i=0,j=0;i<ev.size();)
	{
		if(j>=ev.size() || ev[i].fi-l<ev[j].fi-r)
		{
			long long d=ev[i].fi-l;
			if(opr>=k)
				tmp+=d*cntr;
			if(opl>=k)
				tmp-=d*cntl;
			l+=d;
			r+=d;
			if(ev[i].se==0)
				cntl++;
			else if(ev[i].se==1)
				cntl--;
			else if(ev[i].se==2)
				opl++;
			else
				opl--;
			i++;
		}
		else
		{
			long long d=ev[j].fi-r;
			if(opr>=k)
				tmp+=d*cntr;
			if(opl>=k)
				tmp-=d*cntl;
			l+=d;
			r+=d;
			if(ev[j].se==0)
				cntr++;
			else if(ev[j].se==1)
				cntr--;
			else if(ev[j].se==2)
				opr++;
			else
				opr--;
			j++;
		}
		//cerr<<l<<" "<<r<<" "<<tmp<<"\n";
		ans=max(ans,tmp);
	}
	cout<<ans<<"\n";
	return 0;
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i=0,j=0;i<ev.size();)
      |                  ~^~~~~~~~~~
autobahn.cpp:33:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   if(j>=ev.size() || ev[i].fi-l<ev[j].fi-r)
      |      ~^~~~~~~~~~~

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