Submission #420949

#	Time	Username	Problem	Language	Result	Execution time	Memory
420949		Nicholas_Patrick	Autobahn (COI21_autobahn)	C++17	100 / 100	151 ms	21944 KiB

autobahn

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
 
struct person{
	int l, r, t;
};
struct event{
	int type, time;
	event(int a, int b):type(a), time(b){}
	bool operator<(event rhs)const{
		return time<rhs.time;
	}
};
int main(){
	int n, k, x;
	scanf("%d%d%d", &n, &k, &x);
	vector<person> people(n);
	vector<event> events;
	for(auto& i : people){
		scanf("%d%d%d", &i.l, &i.t, &i.r), i.l--;
		i.t+=i.l;
		events.emplace_back(0, i.l);
		events.emplace_back(1, i.r);
		events.emplace_back(4, i.l+x);
		events.emplace_back(4, i.r-x);
		if(i.t<i.r){
			events.emplace_back(2, i.t);
			events.emplace_back(3, i.r);
			events.emplace_back(4, i.t+x);
		}
	}
	vector<long long> prefixhappy{0};
	sort(events.begin(), events.end());
	int lastTime=events[0].time;
	int count=0, pay=0;
	for(auto i : events){
		prefixhappy.push_back(prefixhappy.back()+(long long)(count>=k)*pay*(i.time-lastTime));
		lastTime=i.time;
		if(i.type==0)
			count++;
		if(i.type==1)
			count--;
		if(i.type==2)
			pay++;
		if(i.type==3)
			pay--;
	}
	long long ans=0;
	for(int i=1, j=0; i<prefixhappy.size(); i++){
		while(j+1<prefixhappy.size() and events[j-1].time+x<events[i-1].time)
			j++;
		ans=max(ans, prefixhappy[i]-prefixhappy[j]);
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=1, j=0; i<prefixhappy.size(); i++){
      |                    ~^~~~~~~~~~~~~~~~~~~
autobahn.cpp:52:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   while(j+1<prefixhappy.size() and events[j-1].time+x<events[i-1].time)
      |         ~~~^~~~~~~~~~~~~~~~~~~
autobahn.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d%d%d", &n, &k, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
autobahn.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   scanf("%d%d%d", &i.l, &i.t, &i.r), i.l--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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