/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2e5 + 10;
struct road
{
int a, b;
} r[maxn];
struct interval
{
int l, r, idx;
interval(int _l = 0, int _r = 0, int _idx = 0)
{
l = _l;
r = _r;
idx = _idx;
}
bool operator < (const interval &it) const
{
return make_pair(l, r) < make_pair(it.l, it.r);
}
};
int n, k, m, q;
bool on_train(int pos, int idx)
{
if (r[idx].a < r[idx].b)
{
return (pos >= r[idx].a && pos <= r[idx].a + k - 1);
}
else
{
return (pos >= r[idx].a - k + 1 && pos <= r[idx].a);
}
}
int to_left[maxn], to_right[maxn];
int solve_query(int s, int t)
{
int lf = s, rf = s, len = 0, nlf = min(lf, to_left[lf]), nrf = max(rf, to_right[rf]);
while(true)
{
if (lf <= t && rf >= t)
return len;
if (nlf == lf && rf == nrf)
break;
int tlf = nlf, trf = nrf;
for (int j = rf + 1; j <= nrf; j ++)
{
if (s > t)
tlf = min(tlf, to_left[j]);
trf = max(trf, to_right[j]);
}
for (int j = nlf; j < lf; j ++)
{
if (s > t)
tlf = min(tlf, to_left[j]);
trf = max(trf, to_right[j]);
}
lf = nlf;
rf = nrf;
len ++;
nlf = tlf;
nrf = trf;
}
return -1;
}
vector < int > tr_add[maxn], tr_rem[maxn];
vector < int > tl_add[maxn], tl_rem[maxn];
bool cmp_rt(road it1, road it2)
{
if (it1.a < it2.a)
return true;
if (it1.a > it2.a)
return false;
return it1.b > it2.b;
}
bool cmp_lt(road it1, road it2)
{
if (it1.a > it2.a)
return true;
if (it1.a < it2.a)
return false;
return it1.b < it2.b;
}
const int maxlog = 20;
int dp[maxlog][maxn], fp[maxlog][maxn], lg[maxn];
pair < int, int > ask[maxn];
int query(int l, int r)
{
if (l > r)
return 0;
int len = lg[r - l + 1] - 1, ans = fp[len][l];
if (to_right[fp[len][r - (1 << len) + 1]] > to_right[ans])
ans = fp[len][r - (1 << len) + 1];
return ans;
}
void solve()
{
cin >> n >> k;
cin >> m;
bool up = true;
for (int i = 1; i <= n; i ++)
{
to_left[i] = n + 1;
to_right[i] = 0;
}
for (int i = 1; i <= m; i ++)
{
cin >> r[i].a >> r[i].b;
if (r[i].a < r[i].b)
{
if (r[i].a < n)
{
tr_add[r[i].a].push_back(r[i].b);
tr_rem[min(n, r[i].a + k - 1)].push_back(r[i].b);
}
///for (int j = r[i].a; j <= min(n, r[i].a + k - 1); j ++)
///to_right[j] = max(to_right[j], r[i].b);
}
else
{
up = false;
if (r[i].a > 1)
{
tl_add[r[i].a].push_back(r[i].b);
tl_rem[max(1, r[i].a - k + 1)].push_back(r[i].b);
}
///for (int j = r[i].a; j >= max(1, r[i].a - k + 1); j --)
/// to_left[j] = min(to_left[j], r[i].b);
}
}
cin >> q;
for (int i = 1; i <= q; i ++)
{
cin >> ask[i].first >> ask[i].second;
if (ask[i].second < ask[i].first)
up = false;
}
multiset < int > st;
for (int i = 1; i <= n; i ++)
{
for (int v : tr_add[i])
{
///cout << "add " << v << endl;
st.insert(v);
}
if (!st.empty())
to_right[i] = *st.rbegin();
for (int v : tr_rem[i])
{
///cout << "rem " << v << endl;
st.erase(st.find(v));
}
}
if (up)
{
for (int i = 1; i <= n; i ++)
fp[0][i] = i;
for (int j = 1; j < maxlog; j ++)
for (int i = 1; i <= n - (1 << j) + 1; i ++)
{
fp[j][i] = fp[j - 1][i];
if (to_right[fp[j - 1][i + (1 << (j - 1))]] > to_right[fp[j][i]])
fp[j][i] = fp[j - 1][i + (1 << (j - 1))];
}
for (int i = 1; i <= n; i ++)
lg[i] = lg[i / 2] + 1;
/**for (int i = 1; i <= n; i ++)
cout << to_right[i] << " ";
cout << endl;*/
for (int i = 1; i <= n; i ++)
{
int mx = query(i + 1, to_right[i]);
if (to_right[mx] == 0)
dp[0][i] = -1;
else
dp[0][i] = mx;
}
for (int j = 1; j < maxlog; j ++)
{
for (int i = 1; i <= n; i ++)
{
if (dp[j - 1][i] == -1)
{
dp[j][i] = -1;
continue;
}
dp[j][i] = dp[j - 1][dp[j - 1][i]];
}
}
/**for (int j = 0; j < 4; j ++, cout << endl)
for (int i = 1; i <= n; i ++)
cout << dp[j][i] << " ";*/
for (int i = 1; i <= q; i ++)
{
int s, t;
s = ask[i].first;
t = ask[i].second;
int jump = 0;
if (to_right[s] >= t)
{
cout << 1 << endl;
continue;
}
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if (dp[bit][s] == -1 || to_right[dp[bit][s]] >= t)
continue;
jump = jump + (1 << bit);
s = dp[bit][s];
}
/**if (to_right[s] >= t)
{
cout << jump + 1 << endl;
continue;
}
cout << dp[0][s] << endl;*/
if (dp[0][s] == -1)
{
cout << -1 << endl;
continue;
}
cout << jump + 2 << endl;
}
/**
12 1
5
1 7
10 12
3 5
8 10
5 9
1
3 12
*/
return;
}
if (k == n - 1)
{
vector < road > rt, lt, frt, flt;
for (int i = 1; i <= m; i ++)
{
if (r[i].a < r[i].b)
rt.push_back(r[i]);
else
lt.push_back(r[i]);
}
sort(lt.begin(), lt.end(), cmp_lt);
sort(rt.begin(), rt.end(), cmp_rt);
int to_r = 0;
for (int i = 0; i < rt.size(); i ++)
{
if (rt[i].b > to_r)
{
to_r = rt[i].b;
frt.push_back(rt[i]);
}
}
int to_l = n + 1;
for (int i = 0; i < lt.size(); i ++)
{
if (lt[i].b < to_l)
{
to_l = lt[i].b;
flt.push_back(lt[i]);
}
}
int pt = 0;
for (int i = 0; i < frt.size(); i ++)
{
while(pt < frt.size() && frt[pt].a <= frt[i].b)
pt ++;
pt --;
if (pt == i)
dp[0][i] = -1;
else
dp[0][i] = pt;
}
pt = 0;
for (int i = 0; i < flt.size(); i ++)
{
while(pt < flt.size() && flt[pt].a >= flt[i].b)
pt ++;
pt --;
if (pt == i)
fp[0][i] = -1;
else
fp[0][i] = pt;
}
for (int j = 1; j < maxlog; j ++)
for (int i = 0; i < frt.size(); i ++)
{
if (dp[j - 1][i] == -1)
{
dp[j][i] = -1;
continue;
}
dp[j][i] = dp[j - 1][dp[j - 1][i]];
}
for (int j = 1; j < maxlog; j ++)
for (int i = 0; i < flt.size(); i ++)
{
if (fp[j - 1][i] == -1)
{
fp[j][i] = -1;
continue;
}
fp[j][i] = fp[j - 1][fp[j - 1][i]];
}
for (int i = 1; i <= q; i ++)
{
int s, t;
s = ask[i].first;
t = ask[i].second;
if (s < t)
{
if (frt.size() == 0)
{
cout << -1 << endl;
continue;
}
int lb = 0, rb = frt.size() - 1;
while(lb <= rb)
{
int mb = (lb + rb) / 2;
if (frt[mb].a > s)
rb = mb - 1;
else
lb = mb + 1;
}
if (rb == -1 || frt[rb].a > s || frt[rb].b < s)
{
cout << -1 << endl;
continue;
}
if (frt[rb].b >= t)
{
cout << 1 << endl;
continue;
}
int jump = 0, pos = rb;
for (int bit = maxlog - 1; bit >= 0; bit --)
{
int id = dp[bit][pos];
if (id == -1 || frt[id].b >= t)
continue;
jump = jump + (1 << bit);
pos = id;
}
if (dp[0][pos] == -1)
{
cout << -1 << endl;
continue;
}
cout << jump + 2 << endl;
}
else
{
if (flt.size() == 0)
{
cout << -1 << endl;
continue;
}
int lb = 0, rb = flt.size() - 1;
while(lb <= rb)
{
int mb = (lb + rb) / 2;
if (flt[mb].a < s)
rb = mb - 1;
else
lb = mb + 1;
}
///cout << flt[rb].a << " : " << flt[rb].b << endl;
if (rb == -1 || flt[rb].b > s || flt[rb].a < s)
{
cout << -1 << endl;
continue;
}
if (flt[rb].b <= t)
{
cout << 1 << endl;
continue;
}
int jump = 0, pos = rb;
for (int bit = maxlog - 1; bit >= 0; bit --)
{
int id = fp[bit][pos];
if (id == -1 || flt[id].b <= t)
continue;
jump = jump + (1 << bit);
pos = id;
}
if (fp[0][pos] == -1)
{
cout << -1 << endl;
continue;
}
cout << jump + 2 << endl;
}
}
return;
}
st.clear();
for (int i = n; i > 0; i --)
{
for (int v : tl_add[i])
st.insert(v);
if (!st.empty())
to_left[i] = *st.begin();
for (int v : tl_rem[i])
st.erase(st.find(v));
}
for (int i = 1; i <= q; i ++)
{
int s, t;
s = ask[i].first;
t = ask[i].second;
int ans = solve_query(s, t);
cout << ans << endl;
}
}
int main()
{
speed();
solve();
return 0;
}
/**
6 5
4
3 1
2 4
5 3
4 6
1
3 2
*/
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:302:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
302 | for (int i = 0; i < rt.size(); i ++)
| ~~^~~~~~~~~~~
Main.cpp:312:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
312 | for (int i = 0; i < lt.size(); i ++)
| ~~^~~~~~~~~~~
Main.cpp:322:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
322 | for (int i = 0; i < frt.size(); i ++)
| ~~^~~~~~~~~~~~
Main.cpp:324:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
324 | while(pt < frt.size() && frt[pt].a <= frt[i].b)
| ~~~^~~~~~~~~~~~
Main.cpp:334:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
334 | for (int i = 0; i < flt.size(); i ++)
| ~~^~~~~~~~~~~~
Main.cpp:336:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
336 | while(pt < flt.size() && flt[pt].a >= flt[i].b)
| ~~~^~~~~~~~~~~~
Main.cpp:346:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
346 | for (int i = 0; i < frt.size(); i ++)
| ~~^~~~~~~~~~~~
Main.cpp:357:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
357 | for (int i = 0; i < flt.size(); i ++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
26528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
29572 KB |
Output is correct |
| 2 |
Correct |
170 ms |
34156 KB |
Output is correct |
| 3 |
Correct |
105 ms |
38068 KB |
Output is correct |
| 4 |
Correct |
148 ms |
36424 KB |
Output is correct |
| 5 |
Correct |
178 ms |
34736 KB |
Output is correct |
| 6 |
Correct |
160 ms |
33916 KB |
Output is correct |
| 7 |
Correct |
177 ms |
38764 KB |
Output is correct |
| 8 |
Correct |
166 ms |
37728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
224 ms |
47368 KB |
Output is correct |
| 2 |
Correct |
130 ms |
43944 KB |
Output is correct |
| 3 |
Correct |
76 ms |
39724 KB |
Output is correct |
| 4 |
Correct |
59 ms |
37196 KB |
Output is correct |
| 5 |
Correct |
46 ms |
35936 KB |
Output is correct |
| 6 |
Correct |
40 ms |
35532 KB |
Output is correct |
| 7 |
Correct |
103 ms |
45776 KB |
Output is correct |
| 8 |
Correct |
11 ms |
19348 KB |
Output is correct |
| 9 |
Correct |
14 ms |
19668 KB |
Output is correct |
| 10 |
Correct |
192 ms |
47016 KB |
Output is correct |
| 11 |
Correct |
260 ms |
51944 KB |
Output is correct |
| 12 |
Correct |
206 ms |
47224 KB |
Output is correct |
| 13 |
Correct |
216 ms |
51324 KB |
Output is correct |
| 14 |
Correct |
13 ms |
19284 KB |
Output is correct |
| 15 |
Correct |
14 ms |
19668 KB |
Output is correct |
| 16 |
Correct |
115 ms |
43948 KB |
Output is correct |
| 17 |
Correct |
201 ms |
52384 KB |
Output is correct |
| 18 |
Correct |
178 ms |
44996 KB |
Output is correct |
| 19 |
Correct |
172 ms |
44928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
