Submission #1002785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002785		Lobo	Autobahn (COI21_autobahn)	C++17	0 / 100	0 ms	348 KiB

autobahn

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

int32_t main() {
	// #ifndef ONLINE_JUDGE
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	// #endif

	int n,k,x;
	map<int,vector<pair<pair<int,int>,int>>> eve;
	cin >> n >> k >> x;
	for(int i = 0; i < n; i++) {
		int l,r,t;
		cin >> l >> t >> r;
		eve[l].pb(mp(mp(l,+1),0));
		eve[r+1].pb(mp(mp(r+1,-1),0));
		if(l+t < r+1) {
			eve[l+t].pb(mp(mp(l+t,+1),1));
			eve[r+1].pb(mp(mp(r+1,-1),1));
		}
	}

	int ant = 0;
	vector<pair<pair<int,int>,int>> extras;
	int people = 0;
	int extra = 0;
	for(auto X : eve) {
		int tempo = X.fr;
		if(people >= k) {
			// ant,tempo-1
			extras.pb(mp(mp(ant,tempo-1),extra));
		}
		ant = tempo;
		for(auto XX : eve[tempo]) {
			int val = XX.fr.sc;
			if(XX.sc == 0) {
				people+= val;
			}
			else {
				extra+= val;
			}
		}
	}

	int ans = 0;
	int sumtot = 0;
	// nao pego nem le nem re inteiros por padrao
	int re = 0;
	for(int le = 0; le < extras.size(); le++) {
		// cout << extras[le].fr.fr << " " << extras[le].fr.sc << " " << extras[le].sc << endl;
		int l = extras[le].fr.fr;
		int r = l+x-1;
		while(re+1 < extras.size() && r >= extras[re+1].fr.fr) {
			sumtot+= (extras[re].fr.sc-extras[re].fr.fr+1)*extras[re].sc;
			re++;
		}
		if(le == re) {
			ans = max(ans, (min(r,extras[re].fr.sc)-extras[re].fr.fr+1)*extras[re].sc);
		}
		else {
			ans = max(ans, sumtot+(min(r,extras[re].fr.sc)-extras[re].fr.fr+1)*extras[re].sc);
			sumtot-= (extras[le].fr.sc-extras[le].fr.fr+1)*extras[le].sc;
		}
	}

	// cout << ans << endl;

	int final = 1e9+1;
	for(int i = 0; i < extras.size(); i++) {
		int l = extras[i].fr.sc;
		extras[i].fr = mp(final-extras[i].fr.sc,final-extras[i].fr.fr);
	}
	reverse(all(extras));
	sumtot = 0;
	re = 0;
	for(int le = 0; le < extras.size(); le++) {
		// cout << final-extras[le].fr.fr << " " << final-extras[le].fr.sc << " " << extras[le].sc << endl;
		// cout << " " << le << " " << extras[le].fr.fr << " " << " " << extras[le].fr.sc << " " << extras[le].sc << endl;

		int l = extras[le].fr.fr;
		int r = l+x-1;
		while(re+1 < extras.size() && r >= extras[re+1].fr.fr) {
			sumtot+= (extras[re].fr.sc-extras[re].fr.fr+1)*extras[re].sc;
			re++;
		}
		if(le == re) {
			ans = max(ans, (min(r,extras[re].fr.sc)-extras[re].fr.fr+1)*extras[re].sc);
			// cout << ans << " " << sumtot << endl;
			re++;
		}
		else {
			ans = max(ans, sumtot+(min(r,extras[re].fr.sc)-extras[re].fr.fr+1)*extras[re].sc);
			// cout << ans << " " << sumtot << " " << le << " " << re << endl;
			sumtot-= (extras[le].fr.sc-extras[le].fr.fr+1)*extras[le].sc;
		}
	}
	cout << ans << endl;


}

Compilation message (stderr)

autobahn.cpp: In function 'int32_t main()':
autobahn.cpp:56:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int le = 0; le < extras.size(); le++) {
      |                  ~~~^~~~~~~~~~~~~~~
autobahn.cpp:60:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   while(re+1 < extras.size() && r >= extras[re+1].fr.fr) {
      |         ~~~~~^~~~~~~~~~~~~~~
autobahn.cpp:76:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 0; i < extras.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
autobahn.cpp:77:7: warning: unused variable 'l' [-Wunused-variable]
   77 |   int l = extras[i].fr.sc;
      |       ^
autobahn.cpp:83:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int le = 0; le < extras.size(); le++) {
      |                  ~~~^~~~~~~~~~~~~~~
autobahn.cpp:89:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   while(re+1 < extras.size() && r >= extras[re+1].fr.fr) {
      |         ~~~~~^~~~~~~~~~~~~~~

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