oj.uz

Submission #420563

# Submission time Handle Problem Language Result Execution time Memory
420563 2021-06-08T12:43:10 Z Nicholas_Patrick Autobahn (COI21_autobahn) C++17
20 / 100
 1 ms 460 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 280 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 204 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 280 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Incorrect 1 ms 460 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 280 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Incorrect 1 ms 460 KB Output isn't correct
13 Halted 0 ms 0 KB -