7476 | 2024. 01. 09 10:00:45 | Ablablabla | A lehető legkevesebb átszállás (50 pont) | cpp14 | Elfogadva 50/50 | 16ms | 9472 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
struct segTree{
int meret = 1;
vector<pii> fa;
void letrehoz(int n){
while(meret < n){
meret *= 2;
}
fa.assign(2 * meret - 1, {0, 0});
for(int i = meret - 1; i < meret - 1 + n; i++){
fa[i].first = i - meret + 1;
}
}
pii keres(int a, int b, int ind, int cel){
if(a == b && a == cel){
return fa[ind];
}
int k = (a + b) / 2;
if(cel <= k){
pii kovi = keres(a, k, 2 * ind + 1, cel);
if(fa[ind].first < kovi.first){
return kovi;
} else{
return fa[ind];
}
} else{
pii kovi = keres(k + 1, b, 2 * ind + 2, cel);
if(fa[ind].first < kovi.first){
return kovi;
} else{
return fa[ind];
}
}
}
void valtoztat(int a, int b, int ind, int kezd, int veg, int uj){
if(veg < a || b < kezd){
return;
} else if(kezd <= a && b <= veg){
if(fa[ind].first < veg){
fa[ind] = {veg, uj};
}
return;
}
int k = (a + b) / 2;
valtoztat(a, k, 2 * ind + 1, kezd, veg, uj);
valtoztat(k + 1, b, 2 * ind + 2, kezd, veg, uj);
return;
}
};
int main()
{
int n, m;
cin >> m >> n;
vector<pii> eleri(n);
segTree fa;
fa.letrehoz(n);
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
a--; b--;
fa.valtoztat(0, fa.meret - 1, 0, a, b, i);
}
int akt = 0;
vector<int> vonalak;
while(akt < n - 1){
pii kovi = fa.keres(0, fa.meret - 1, 0, akt);
if(akt == kovi.first){
cout << "-1\n";
return 0;
}
vonalak.push_back(kovi.second);
akt = kovi.first;
}
cout << vonalak.size() - 1 << "\n";
for(int x : vonalak){
cout << x + 1 << " ";
}
cout << "\n";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1808 KiB | |||
2 | Elfogadva | 0/0 | 14ms | 7512 KiB | |||
3 | Elfogadva | 1/1 | 3ms | 2216 KiB | |||
4 | Elfogadva | 1/1 | 3ms | 2460 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2512 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2540 KiB | |||
7 | Elfogadva | 2/2 | 4ms | 2792 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 3104 KiB | |||
9 | Elfogadva | 2/2 | 4ms | 3152 KiB | |||
10 | Elfogadva | 2/2 | 6ms | 3556 KiB | |||
11 | Elfogadva | 2/2 | 8ms | 5480 KiB | |||
12 | Elfogadva | 2/2 | 8ms | 5776 KiB | |||
13 | Elfogadva | 2/2 | 4ms | 4484 KiB | |||
14 | Elfogadva | 2/2 | 6ms | 5648 KiB | |||
15 | Elfogadva | 2/2 | 7ms | 6076 KiB | |||
16 | Elfogadva | 2/2 | 8ms | 6200 KiB | |||
17 | Elfogadva | 2/2 | 12ms | 8620 KiB | |||
18 | Elfogadva | 2/2 | 13ms | 8948 KiB | |||
19 | Elfogadva | 2/2 | 14ms | 8856 KiB | |||
20 | Elfogadva | 2/2 | 14ms | 8984 KiB | |||
21 | Elfogadva | 2/2 | 14ms | 8980 KiB | |||
22 | Elfogadva | 2/2 | 14ms | 8984 KiB | |||
23 | Elfogadva | 2/2 | 14ms | 8596 KiB | |||
24 | Elfogadva | 2/2 | 14ms | 8676 KiB | |||
25 | Elfogadva | 2/2 | 14ms | 9044 KiB | |||
26 | Elfogadva | 2/2 | 14ms | 9068 KiB | |||
27 | Elfogadva | 2/2 | 16ms | 9256 KiB | |||
28 | Elfogadva | 2/2 | 14ms | 9472 KiB |