Submission #420563

#	Time	Username	Problem	Language	Result	Execution time	Memory
420563		Nicholas_Patrick	Autobahn (COI21_autobahn)	C++17	20 / 100	1 ms	460 KiB

autobahn

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

struct person{
	int l, r, t;
};
struct event{
	int type, time;
	/*
		0: count++
		1: count--
		2: pay++
		3: pay--
		4: do nothing
	*/
	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=-1000000000;
	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=2, j=1; i<prefixhappy.size(); i++){
		while(j+1<prefixhappy.size() and events[j].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:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i=2, j=1; i<prefixhappy.size(); i++){
      |                    ~^~~~~~~~~~~~~~~~~~~
autobahn.cpp:59:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   while(j+1<prefixhappy.size() and events[j].time+x<=events[i-1].time)
      |         ~~~^~~~~~~~~~~~~~~~~~~
autobahn.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d%d%d", &n, &k, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
autobahn.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   scanf("%d%d%d", &i.l, &i.t, &i.r), i.l--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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