| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1002794 |
2024-06-19T19:44:44 Z |
teesla |
Autobahn (COI21_autobahn) |
C++14 |
|
1000 ms |
88744 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int, ii> iii;
typedef long long int ll;
struct seg{
vector<ll> extra, qnt;
int n;
seg(){};
seg(int x){n = x; qnt.assign(4*(x+1), 0); extra.assign(4*(x+1), 0);}
void addQnt(int pos, int i, int f, int l, int r){
if(l<=i and f<=r){
qnt[pos] += 1;
return;
}
int meio = (i+f)/2;
if(l <=meio) addQnt(2*pos+1, i, meio, l, r);
if(r > meio) addQnt(2*pos+2, meio+1, f, l, r);
return;
}
void addExtra(int pos, int i, int f, int l, int r){
if(l <= i and f<= r){
extra[pos] += 1;
return;
}
int meio = (i+f)/2;
if(l <= meio) addExtra(2*pos+1, i, meio, l, r);
if(r > meio) addExtra(2*pos+2, meio+1, f, l, r);
return;
}
pair<ll,ll> query(int pos, int i, int f, int idx){
if(i == f and i == idx){
return {extra[pos], qnt[pos]};
}
int meio = (i+f)/2;
pair<ll,ll> res;
if(idx <= meio) res = query(2*pos+1, i, meio, idx);
else res = query(2*pos+2, meio + 1, f, idx);
res.first += extra[pos];
res.second += qnt[pos];
return res;
}
void addQnt(int l, int r){ addQnt(0,0,n,l,r); return;}
void addExtra(int l, int r) {addExtra(0,0,n,l,r); return;}
pair<ll,ll> query(int idx){
return query(0,0,n,idx);
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,k,x; cin >> n >> k >> x;
vector<ll> aux;
vector<iii> v;
for(int i=0; i<n; i++){
ll l,t,r; cin >> l >> t >> r;
aux.push_back(l-1);
aux.push_back(l); aux.push_back(l+t-1); aux.push_back(l + t); aux.push_back(r); aux.push_back(r + 1);
v.push_back({l, {t,r}});
}
sort(aux.begin(), aux.end());
vector<ll> aux2;
aux2.push_back(aux[0]);
for(int i=1; i<aux.size(); i++){
if(aux[i] == aux[i-1]) continue;
else aux2.push_back(aux[i]);
}
aux = aux2;
ll cont = 0;
map<ll,ll> comp;
for(auto i: aux){
if(comp[i] == 0){
cont++;
comp[i] = cont;
}
}
seg tree(cont);
for(auto i: v){
ll l = i.first, t = i.second.first, r = i.second.second;
//cout << endl << endl;
tree.addQnt(comp[l],comp[r]);
tree.addExtra(comp[l+t], comp[r]);
}
long long int maior = 0;
long long int sum = 0;
ll i=0, f = 1;
ii aa = tree.query(comp[aux[0]]);
if(aa.second >= k){sum += aa.first; maior = sum;}
while(f< aux.size()){
ll l = aux[i], r = aux[f];
if(aux[f] == aux[f-1]){
f++;
continue;
}
if(r - l >= x){
ll anterior = aux[f-1];
ll sobra = anterior-l + 1;
long long int outro = sum;
sobra = x - sobra;
ii valorAnterior = tree.query(comp[anterior]);
if(valorAnterior.second >= k){
outro += sobra*valorAnterior.first;
}
maior = max(maior, outro);
sobra = aux[i+1] - aux[i];
valorAnterior = tree.query(comp[aux[i]]);
if(valorAnterior.second >= k){
sum -= sobra*valorAnterior.first;
}
i++;
}
else{
ll anterior = aux[f-1];
ll sobra = aux[f] - aux[f-1] -1;
ii valorAnterior = tree.query(comp[aux[f-1]]);
if(valorAnterior.second >= k){
sum += sobra*valorAnterior.first;
}
ii valorAtual = tree.query(comp[aux[f]]);
if(valorAtual.second >= k){
sum += valorAtual.first;
}
maior = max(sum, maior);
f++;
}
}
sum = 0;
f = aux.size()-1; i = aux.size() - 2;
aa = tree.query(comp[aux[f]]);
if(aa.second >= k){sum += aa.first; maior = max(maior, sum);}
while(i>=0){
ll l = aux[i], r = aux[f];
if(aux[i] == aux[i+1]){
i--; continue;
}
if(r - l >= x){
ll anterior = aux[i+1];
ll sobra = r - anterior + 1;
sobra = x-sobra;
ll outro = sum;
ii valorAnterior = tree.query(comp[anterior]);
if(valorAnterior.second >= k){
outro += sobra*valorAnterior.first;
}
maior = max(maior, outro);
sobra = aux[f] - aux[f-1];
valorAnterior = tree.query(comp[aux[f]]);
if(valorAnterior.second >= k){
sum -= sobra*valorAnterior.first;
}
f--;
}
else{
ll sobra = aux[i+1] - aux[i] - 1;
ii valorAnterior = tree.query(comp[aux[i+1]]);
if(valorAnterior.second >= k){
sum += sobra*valorAnterior.first;
}
ii valorAtual = tree.query(comp[aux[i]]);
if(valorAtual.second >= k){
sum += valorAtual.first;
}
maior = max(maior, sum);
i--;
}
}
cout << maior << '\n';
}
Compilation message
autobahn.cpp: In function 'int main()':
autobahn.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i=1; i<aux.size(); i++){
| ~^~~~~~~~~~~
autobahn.cpp:109:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | while(f< aux.size()){
| ~^~~~~~~~~~~~
autobahn.cpp:139:16: warning: unused variable 'anterior' [-Wunused-variable]
139 | ll anterior = aux[f-1];
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
452 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
452 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
2 ms |
604 KB |
Output is correct |
| 13 |
Correct |
2 ms |
604 KB |
Output is correct |
| 14 |
Correct |
2 ms |
604 KB |
Output is correct |
| 15 |
Correct |
2 ms |
604 KB |
Output is correct |
| 16 |
Correct |
3 ms |
604 KB |
Output is correct |
| 17 |
Correct |
2 ms |
604 KB |
Output is correct |
| 18 |
Correct |
2 ms |
604 KB |
Output is correct |
| 19 |
Correct |
2 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 |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
452 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
2 ms |
604 KB |
Output is correct |
| 13 |
Correct |
2 ms |
604 KB |
Output is correct |
| 14 |
Correct |
2 ms |
604 KB |
Output is correct |
| 15 |
Correct |
2 ms |
604 KB |
Output is correct |
| 16 |
Correct |
3 ms |
604 KB |
Output is correct |
| 17 |
Correct |
2 ms |
604 KB |
Output is correct |
| 18 |
Correct |
2 ms |
604 KB |
Output is correct |
| 19 |
Correct |
2 ms |
604 KB |
Output is correct |
| 20 |
Correct |
1 ms |
604 KB |
Output is correct |
| 21 |
Execution timed out |
1062 ms |
88744 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
