| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1002785 |
2024-06-19T19:40:36 Z |
Lobo |
Autobahn (COI21_autobahn) |
C++17 |
|
0 ms |
348 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 << 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
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) {
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
