Puoi leggere e provare a risolvere il problema visitando la piattaforma Terry.
Notiamo che, dato che ci possiamo spostare solo in alto o verso destra, le coordinate che visitiamo sono crescenti (e anche le coordinate ).
Questo significa che, dato un insieme di città, possiamo visitarle solo in ordine crescente di coordinata (e anche di coordinata ). Se rappresentiamo le coordinate come coppie , un modo per verificare se possiamo visitarle tutte è quindi ordinarle in ordine lessicografico (usando sort), e controllare se sia gli sia gli sono (debolmente) crescenti.
Se effettuiamo questo controllo per tutti i prefissi, impieghiamo per ogni prefisso, quindi in totale.
Questa soluzione, se implementata con cura, riesce a totalizzare punteggio pieno, ma esistono soluzioni con complessità molto minore.
Iteriamo sui prefissi da sinistra a destra. Per ogni prefisso, invece di ordinare tutte le città, possiamo usare l'ordinamento del prefisso precedente e inserire la nuova città (impiegando ).
In questo modo controlliamo prefissi, ciascuno in , e la complessità finale è .
Possiamo utilizzare l'idea della soluzione precedente, usando una struttura dati per inserire città in modo efficiente. In particolare, ci serve una struttura dati in grado di mantenere elementi in ordine crescente e di inserire elementi in meno di . Possiamo ad esempio utilizzare un set o una map.
In questo modo controlliamo prefissi, ciascuno in , e la complessità finale è .
Notiamo che, se un prefisso non è interamente visitabile, non lo sono neanche i prefissi successivi. Questo significa che esiste un indice tale che i prefissi fino a sono gli unici interamente visitabili. Possiamo quindi effettuare una binary search sull'indice .
In questo modo controlliamo solo prefissi, ciascuno in , e la complessità finale è .
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
void solve(int t) {
int N;
cin >> N;
vector<int> X(N), Y(N);
for (int i = 0; i < N; ++i) {
cin >> X[i] >> Y[i];
}
map<int, pair<int, int>> pos;
pos[-1] = {-1, -1};
pos[1e9 + 10] = {1e9 + 10, 1e9 + 10};
int risposta = 0;
for (int i = 0; i < N; i++) {
int x = X[i];
int y = Y[i];
auto it = pos.lower_bound(x);
if (it != pos.end() && it->first == x) {
it->second.first = min(it->second.first, y);
it->second.second = max(it->second.second, y);
} else {
pos[x] = {y, y};
}
auto next = pos.lower_bound(x + 1);
auto prev = std::prev(pos.lower_bound(x));
if (prev->second.second > y)
break;
if (next->second.first < y)
break;
risposta++;
}
cout << "Case #" << t << ": " << risposta << "\n";
}
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
solve(t);
}
return 0;
}
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
#define X first
#define Y second
void solve(int t){
int N; cin >> N;
vector<pair<int, int>> v(N);
for(auto &[x,y]: v)cin >> x >> y;
int ans = 0;
for(int j = 1<<20; j; j/=2){
int bs = ans + j;
if(bs > N)continue;
vector<pair<int,int>> cur(v.begin(), v.begin() + bs);
sort(cur.begin(), cur.end());
bool ok = 1;
for(int i = 1; i < bs; ++i){
if(cur[i].Y < cur[i-1].Y)ok = 0;
}
if(ok)ans = bs;
}
cout << "Case #" << t << ": ";
cout << ans << endl;
}
int main(int argc, char **argv){
ios::sync_with_stdio(false);
int T; cin >> T;
for(int t = 1; t <= T; ++t) {
solve(t);
}
}