#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5 + 5;
int DP[20][N];
void Solve()
{
int n;
cin >> n;
vector<int> max_left(n + 1, -1);
vector<int> l(n + 1), r(n + 1);
set<pair<int, int> > s;
for(int i = 1; i <= n; i++)
{
cin >> l[i] >> r[i];
}
int left = n;
for(int right = n; right > 0; right--)
{
while(left > 0)
{
auto idx = s.lower_bound(make_pair(l[left], r[left]));
if(idx == s.end())
{
s.insert(make_pair(l[left], r[left]));
left--;
continue;
}
if(((*idx).first) <= r[left])
{
// cout << "left = " << left << ", right = " << right << ", (*idx).first = " << (*idx).first << "\n";
break;
}
s.insert(make_pair(l[left], r[left]));
left--;
}
//actually from left + 1, but since left + 1 will be taken, we assign it as left
max_left[right] = left;
s.erase(make_pair(l[right], r[right]));
}
for(int i = 1; i <= n; i++)
{
// cout << max_left[i] << " ";
DP[0][i] = max_left[i];
}
// cout << "\n";
left = n;
s.clear();
for(int right = n; right > 0; right--)
{
while(left > 0)
{
auto idx = s.lower_bound(make_pair(l[left], r[left]));
// cout << "(*idx).first = " << (*idx).first << ", (*idx).second = " << (*idx).second << "\n";
if(s.size() == 0)
{
// cout << "left = " << left << ", right = " << right << ", at s.size() == 0\n";
// cout << "left = " << left << ", right = " << right << ", (*idx).first = " << (*idx).first << ", (*idx).second = " << (*idx).second << "\n";
s.insert(make_pair(l[left], r[left]));
left--;
continue;
}
idx = prev(idx);
if(idx == prev(s.begin()))
{
// cout << "left = " << left << ", right = " << right << ", at s.begin() after reducing one number\n";
// cout << "left = " << left << ", right = " << right << ", (*idx).first = " << (*idx).first << ", (*idx).second = " << (*idx).second << "\n";
s.insert(make_pair(l[left], r[left]));
left--;
continue;
}
if(((*idx).second) >= l[left])
{
// cout << "left = " << left << ", right = " << right << ", (*idx).first = " << (*idx).first << ", (*idx).second = " << (*idx).second << "\n";
break;
}
// cout << "left = " << left << ", right = " << right << ", nothing happened\n";
// cout << "left = " << left << ", right = " << right << ", (*idx).first = " << (*idx).first << ", (*idx).second = " << (*idx).second << "\n";
s.insert(make_pair(l[left], r[left]));
left--;
}
max_left[right] = max(max_left[right], left);
s.erase(make_pair(l[right], r[right]));
}
for(int i = 1; i <= n; i++)
{
// cout << max_left[i] << " ";
DP[0][i] = max_left[i];
}
// cout << "\n";
for(int i = 1; i < 20; i++)
{
for(int j = 1; j <= n; j++)
{
if(DP[i - 1][j] == 0)
{
DP[i][j] = 0;
}
else
{
DP[i][j] = DP[i - 1][DP[i - 1][j]];
}
}
}
int queries;
cin >> queries;
while(queries--)
{
int left, right;
cin >> left >> right;
int ans = 0;
int cur_idx = right;
for(int i = 19; i >= 0; i--)
{
if(DP[i][cur_idx] >= left)
{
cur_idx = DP[i][cur_idx];
ans += (1 << i);
}
}
cout << ans + 1 << "\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
38380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
40296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
38380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
