| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1002787 |
2024-06-19T19:42:12 Z |
Lobo |
Autobahn (COI21_autobahn) |
C++17 |
|
322 ms |
45360 KB |
#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 << 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;
int final = 1e9+1;
for(int i = 0; i < extras.size(); i++) {
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
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:62: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]
62 | while(re+1 < extras.size() && r >= extras[re+1].fr.fr) {
| ~~~~~^~~~~~~~~~~~~~~
autobahn.cpp:81: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]
81 | for(int i = 0; i < extras.size(); i++) {
| ~~^~~~~~~~~~~~~~~
autobahn.cpp:87: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]
87 | for(int le = 0; le < extras.size(); le++) {
| ~~~^~~~~~~~~~~~~~~
autobahn.cpp:93: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]
93 | while(re+1 < extras.size() && r >= extras[re+1].fr.fr) {
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
440 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
440 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
600 KB |
Output is correct |
| 13 |
Correct |
1 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1 ms |
604 KB |
Output is correct |
| 15 |
Correct |
1 ms |
604 KB |
Output is correct |
| 16 |
Correct |
1 ms |
584 KB |
Output is correct |
| 17 |
Correct |
1 ms |
600 KB |
Output is correct |
| 18 |
Correct |
1 ms |
604 KB |
Output is correct |
| 19 |
Correct |
1 ms |
604 KB |
Output is correct |
| 20 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
440 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
600 KB |
Output is correct |
| 13 |
Correct |
1 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1 ms |
604 KB |
Output is correct |
| 15 |
Correct |
1 ms |
604 KB |
Output is correct |
| 16 |
Correct |
1 ms |
584 KB |
Output is correct |
| 17 |
Correct |
1 ms |
600 KB |
Output is correct |
| 18 |
Correct |
1 ms |
604 KB |
Output is correct |
| 19 |
Correct |
1 ms |
604 KB |
Output is correct |
| 20 |
Correct |
1 ms |
604 KB |
Output is correct |
| 21 |
Correct |
322 ms |
45356 KB |
Output is correct |
| 22 |
Correct |
295 ms |
45224 KB |
Output is correct |
| 23 |
Correct |
281 ms |
45252 KB |
Output is correct |
| 24 |
Correct |
263 ms |
45252 KB |
Output is correct |
| 25 |
Correct |
256 ms |
45360 KB |
Output is correct |
| 26 |
Correct |
310 ms |
45252 KB |
Output is correct |
| 27 |
Correct |
296 ms |
45308 KB |
Output is correct |
| 28 |
Correct |
287 ms |
45188 KB |
Output is correct |
| 29 |
Correct |
298 ms |
45252 KB |
Output is correct |
