Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 2e5 + 10;
- const int MAXK = 30;
- int pai[MAXN];
- int dp[MAXN][MAXK];
- struct filme
- {
- int L, R;
- filme(int left, int right) {L = left; R = right;}
- bool operator<(filme outro)
- {
- if (R == outro.R) return L > outro.L;
- return R < outro.R;
- }
- };
- vector<filme> Filmes;
- vector<filme> Uteis;
- int BUSCA_BINARIA(int val, int N)
- {
- int ini = 0; int fim = N;
- if (val > Uteis[fim].L) return -1;
- while (ini < fim)
- {
- int m = (ini + fim) / 2;
- if (Uteis[m].L >= val) fim = m;
- else ini = m+1;
- }
- return fim;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int N, Q;
- cin >> N >> Q;
- for (int i = 0; i < N; i++)
- {
- int X, Y;
- cin >> X >> Y;
- Filmes.emplace_back(X, Y);
- }
- sort(Filmes.begin(), Filmes.end());
- int ultL = -1;
- for (int i = 0; i < Filmes.size(); i++)
- {
- if (Filmes[i].L <= ultL) continue;
- ultL = Filmes[i].L;
- Uteis.push_back(Filmes[i]);
- }
- Uteis.emplace_back(1e9 + 10, 1e9 + 10);
- pai[Uteis.size()-1] = Uteis.size()-1;
- for (int i = 0; i < Uteis.size(); i++)
- {
- int id = BUSCA_BINARIA(Uteis[i].R, Uteis.size()-2);
- if (id == -1) pai[i] = Uteis.size()-1;
- else pai[i] = id;
- }
- for (int i = 0; i < Uteis.size(); i++)
- {
- dp[i][0] = pai[i];
- }
- for (int k = 1; k < MAXK; k++)
- {
- for (int i = 0; i < Uteis.size(); i++)
- {
- dp[i][k] = dp[ dp[i][k-1] ][k-1];
- }
- }
- for (int q = 0; q < Q; q++)
- {
- int A, B;
- cin >> A >> B;
- A = BUSCA_BINARIA(A, Uteis.size()-2);
- if (A == -1) {cout << "0" << '\n'; continue;}
- int resp = 0;
- if (B >= Uteis[A].R) resp++;
- else
- {
- cout << "0" << '\n';
- continue;
- }
- for (int k = MAXK-1; k >= 0; k--)
- {
- if (Uteis[dp[A][k]].R > B) continue;
- resp += (1 << k);
- A = dp[A][k];
- }
- cout << resp << '\n';
- }
- }
Add Comment
Please, Sign In to add comment
