#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
#define int long long
signed main(signed argc, char *argv[])
{
int N, M, s, e;
cin >> N >> M;
vector<pair<int, int>> sorted;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq, cpq;
map<int, int> vals;
for (int i = 0; i < N; i++)
{
cin >> s >> e;
if (s > e)
e += M;
vals[s] = max(vals[s], e);
}
map<int, int> endvals;
while (!vals.empty())
{
sorted.push_back(*vals.begin());
cpq.push(*vals.begin());
endvals[vals.begin()->second] = sorted.size() - 1;
vals.erase(vals.begin());
}
int crntmax = cpq.top().second;
while (!cpq.empty())
{
if (cpq.top().second > crntmax)
{
crntmax = cpq.top().second;
pq.push(cpq.top());
sorted.push_back(cpq.top());
endvals[cpq.top().second] = sorted.size() - 1;
}
cpq.pop();
}
N = sorted.size();
vector<vector<int>> parent(31, vector<int>(N, -1));
auto currvals = pq.top();
int currmax = pq.top().second;
int currind = 0;
pq.pop();
for (auto i : endvals)
{
while (currvals.first <= i.first)
{
if (currmax < currvals.second)
{
currmax = currvals.second;
currind = N - pq.size() - 1;
}
if (pq.empty())
currvals.first = LLONG_MAX;
else
{
currvals = pq.top();
pq.pop();
}
}
if (currind == i.second)
parent[0][i.second] = -1;
else
parent[0][i.second] = currind;
}
for (int i = 1; i < 31; i++)
{
for (int j = 0; j < N; j++)
{
if (parent[i - 1][j] == -1)
parent[i][j] = -1;
else
parent[i][j] = parent[i - 1][parent[i - 1][j]];
}
}
int ans = LLONG_MAX;
for (int i = 0; i < N; i++)
{
int qq = i;
int b = 0;
int currans = 0;
int a = sorted[i].first + M;
for (int j = 30; j >= 0; j--)
{
int abc = parent[j][qq];
if (abc != -1)
{
if (sorted[abc].second >= a)
currans = b + (1 << j);
else
b += 1 << j, qq = abc;
}
}
if (currans != 0)
ans = min(ans, currans + 1);
}
if (ans == LLONG_MAX)
cout << "-1\n";
else
cout << ans << '\n';
}
Compilation message
Main.cpp: In function 'int main(int, char**)':
Main.cpp:58:23: error: 'LLONG_MAX' was not declared in this scope
58 | currvals.first = LLONG_MAX;
| ^~~~~~~~~
Main.cpp:5:1: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
4 | #include <queue>
+++ |+#include <climits>
5 | using namespace std;
Main.cpp:80:12: error: 'LLONG_MAX' was not declared in this scope
80 | int ans = LLONG_MAX;
| ^~~~~~~~~
Main.cpp:80:12: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
