/**
____ ____ ____ ____ ____ ____
||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 ++)
{
tlf = min(tlf, to_left[j]);
trf = max(trf, to_right[j]);
}
for (int j = nlf; j < lf; j ++)
{
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:300:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
300 | for (int i = 0; i < rt.size(); i ++)
| ~~^~~~~~~~~~~
Main.cpp:310:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
310 | for (int i = 0; i < lt.size(); i ++)
| ~~^~~~~~~~~~~
Main.cpp:320:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
320 | for (int i = 0; i < frt.size(); i ++)
| ~~^~~~~~~~~~~~
Main.cpp:322:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
322 | while(pt < frt.size() && frt[pt].a <= frt[i].b)
| ~~~^~~~~~~~~~~~
Main.cpp:332:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
332 | for (int i = 0; i < flt.size(); i ++)
| ~~^~~~~~~~~~~~
Main.cpp:334:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
334 | while(pt < flt.size() && flt[pt].a >= flt[i].b)
| ~~~^~~~~~~~~~~~
Main.cpp:344:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
344 | for (int i = 0; i < frt.size(); i ++)
| ~~^~~~~~~~~~~~
Main.cpp:355:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
355 | for (int i = 0; i < flt.size(); i ++)
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19156 KB |
Output is correct |
2 |
Correct |
12 ms |
19088 KB |
Output is correct |
3 |
Correct |
9 ms |
19156 KB |
Output is correct |
4 |
Correct |
10 ms |
19156 KB |
Output is correct |
5 |
Correct |
10 ms |
19156 KB |
Output is correct |
6 |
Correct |
10 ms |
19368 KB |
Output is correct |
7 |
Correct |
12 ms |
19156 KB |
Output is correct |
8 |
Correct |
10 ms |
19120 KB |
Output is correct |
9 |
Correct |
10 ms |
19284 KB |
Output is correct |
10 |
Correct |
11 ms |
19156 KB |
Output is correct |
11 |
Correct |
11 ms |
19156 KB |
Output is correct |
12 |
Correct |
10 ms |
19320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19156 KB |
Output is correct |
2 |
Correct |
12 ms |
19088 KB |
Output is correct |
3 |
Correct |
9 ms |
19156 KB |
Output is correct |
4 |
Correct |
10 ms |
19156 KB |
Output is correct |
5 |
Correct |
10 ms |
19156 KB |
Output is correct |
6 |
Correct |
10 ms |
19368 KB |
Output is correct |
7 |
Correct |
12 ms |
19156 KB |
Output is correct |
8 |
Correct |
10 ms |
19120 KB |
Output is correct |
9 |
Correct |
10 ms |
19284 KB |
Output is correct |
10 |
Correct |
11 ms |
19156 KB |
Output is correct |
11 |
Correct |
11 ms |
19156 KB |
Output is correct |
12 |
Correct |
10 ms |
19320 KB |
Output is correct |
13 |
Correct |
17 ms |
19288 KB |
Output is correct |
14 |
Correct |
16 ms |
19304 KB |
Output is correct |
15 |
Correct |
10 ms |
19156 KB |
Output is correct |
16 |
Correct |
13 ms |
19344 KB |
Output is correct |
17 |
Correct |
13 ms |
19284 KB |
Output is correct |
18 |
Correct |
11 ms |
19540 KB |
Output is correct |
19 |
Correct |
16 ms |
19284 KB |
Output is correct |
20 |
Correct |
15 ms |
19308 KB |
Output is correct |
21 |
Correct |
10 ms |
19284 KB |
Output is correct |
22 |
Correct |
11 ms |
19492 KB |
Output is correct |
23 |
Correct |
13 ms |
19264 KB |
Output is correct |
24 |
Correct |
11 ms |
19604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
26312 KB |
Output is correct |
2 |
Correct |
62 ms |
26404 KB |
Output is correct |
3 |
Correct |
66 ms |
27732 KB |
Output is correct |
4 |
Correct |
66 ms |
25876 KB |
Output is correct |
5 |
Correct |
184 ms |
31728 KB |
Output is correct |
6 |
Correct |
133 ms |
34764 KB |
Output is correct |
7 |
Correct |
152 ms |
34104 KB |
Output is correct |
8 |
Correct |
107 ms |
27156 KB |
Output is correct |
9 |
Correct |
81 ms |
27048 KB |
Output is correct |
10 |
Correct |
153 ms |
30136 KB |
Output is correct |
11 |
Correct |
142 ms |
35676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
29264 KB |
Output is correct |
2 |
Correct |
192 ms |
34052 KB |
Output is correct |
3 |
Correct |
119 ms |
38060 KB |
Output is correct |
4 |
Correct |
142 ms |
36408 KB |
Output is correct |
5 |
Correct |
172 ms |
34764 KB |
Output is correct |
6 |
Correct |
168 ms |
33928 KB |
Output is correct |
7 |
Correct |
175 ms |
38808 KB |
Output is correct |
8 |
Correct |
164 ms |
37796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
236 ms |
46040 KB |
Output is correct |
2 |
Correct |
129 ms |
43220 KB |
Output is correct |
3 |
Correct |
89 ms |
39652 KB |
Output is correct |
4 |
Correct |
75 ms |
37220 KB |
Output is correct |
5 |
Correct |
48 ms |
35852 KB |
Output is correct |
6 |
Correct |
51 ms |
35512 KB |
Output is correct |
7 |
Correct |
103 ms |
45640 KB |
Output is correct |
8 |
Correct |
10 ms |
19248 KB |
Output is correct |
9 |
Correct |
14 ms |
19744 KB |
Output is correct |
10 |
Correct |
207 ms |
46904 KB |
Output is correct |
11 |
Correct |
246 ms |
51908 KB |
Output is correct |
12 |
Correct |
234 ms |
47244 KB |
Output is correct |
13 |
Correct |
226 ms |
51348 KB |
Output is correct |
14 |
Correct |
10 ms |
19244 KB |
Output is correct |
15 |
Correct |
11 ms |
19704 KB |
Output is correct |
16 |
Correct |
111 ms |
44004 KB |
Output is correct |
17 |
Correct |
186 ms |
52416 KB |
Output is correct |
18 |
Correct |
194 ms |
45224 KB |
Output is correct |
19 |
Correct |
170 ms |
45008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19156 KB |
Output is correct |
2 |
Correct |
12 ms |
19088 KB |
Output is correct |
3 |
Correct |
9 ms |
19156 KB |
Output is correct |
4 |
Correct |
10 ms |
19156 KB |
Output is correct |
5 |
Correct |
10 ms |
19156 KB |
Output is correct |
6 |
Correct |
10 ms |
19368 KB |
Output is correct |
7 |
Correct |
12 ms |
19156 KB |
Output is correct |
8 |
Correct |
10 ms |
19120 KB |
Output is correct |
9 |
Correct |
10 ms |
19284 KB |
Output is correct |
10 |
Correct |
11 ms |
19156 KB |
Output is correct |
11 |
Correct |
11 ms |
19156 KB |
Output is correct |
12 |
Correct |
10 ms |
19320 KB |
Output is correct |
13 |
Correct |
17 ms |
19288 KB |
Output is correct |
14 |
Correct |
16 ms |
19304 KB |
Output is correct |
15 |
Correct |
10 ms |
19156 KB |
Output is correct |
16 |
Correct |
13 ms |
19344 KB |
Output is correct |
17 |
Correct |
13 ms |
19284 KB |
Output is correct |
18 |
Correct |
11 ms |
19540 KB |
Output is correct |
19 |
Correct |
16 ms |
19284 KB |
Output is correct |
20 |
Correct |
15 ms |
19308 KB |
Output is correct |
21 |
Correct |
10 ms |
19284 KB |
Output is correct |
22 |
Correct |
11 ms |
19492 KB |
Output is correct |
23 |
Correct |
13 ms |
19264 KB |
Output is correct |
24 |
Correct |
11 ms |
19604 KB |
Output is correct |
25 |
Correct |
48 ms |
26312 KB |
Output is correct |
26 |
Correct |
62 ms |
26404 KB |
Output is correct |
27 |
Correct |
66 ms |
27732 KB |
Output is correct |
28 |
Correct |
66 ms |
25876 KB |
Output is correct |
29 |
Correct |
184 ms |
31728 KB |
Output is correct |
30 |
Correct |
133 ms |
34764 KB |
Output is correct |
31 |
Correct |
152 ms |
34104 KB |
Output is correct |
32 |
Correct |
107 ms |
27156 KB |
Output is correct |
33 |
Correct |
81 ms |
27048 KB |
Output is correct |
34 |
Correct |
153 ms |
30136 KB |
Output is correct |
35 |
Correct |
142 ms |
35676 KB |
Output is correct |
36 |
Correct |
76 ms |
29264 KB |
Output is correct |
37 |
Correct |
192 ms |
34052 KB |
Output is correct |
38 |
Correct |
119 ms |
38060 KB |
Output is correct |
39 |
Correct |
142 ms |
36408 KB |
Output is correct |
40 |
Correct |
172 ms |
34764 KB |
Output is correct |
41 |
Correct |
168 ms |
33928 KB |
Output is correct |
42 |
Correct |
175 ms |
38808 KB |
Output is correct |
43 |
Correct |
164 ms |
37796 KB |
Output is correct |
44 |
Correct |
236 ms |
46040 KB |
Output is correct |
45 |
Correct |
129 ms |
43220 KB |
Output is correct |
46 |
Correct |
89 ms |
39652 KB |
Output is correct |
47 |
Correct |
75 ms |
37220 KB |
Output is correct |
48 |
Correct |
48 ms |
35852 KB |
Output is correct |
49 |
Correct |
51 ms |
35512 KB |
Output is correct |
50 |
Correct |
103 ms |
45640 KB |
Output is correct |
51 |
Correct |
10 ms |
19248 KB |
Output is correct |
52 |
Correct |
14 ms |
19744 KB |
Output is correct |
53 |
Correct |
207 ms |
46904 KB |
Output is correct |
54 |
Correct |
246 ms |
51908 KB |
Output is correct |
55 |
Correct |
234 ms |
47244 KB |
Output is correct |
56 |
Correct |
226 ms |
51348 KB |
Output is correct |
57 |
Correct |
10 ms |
19244 KB |
Output is correct |
58 |
Correct |
11 ms |
19704 KB |
Output is correct |
59 |
Correct |
111 ms |
44004 KB |
Output is correct |
60 |
Correct |
186 ms |
52416 KB |
Output is correct |
61 |
Correct |
194 ms |
45224 KB |
Output is correct |
62 |
Correct |
170 ms |
45008 KB |
Output is correct |
63 |
Execution timed out |
2074 ms |
26924 KB |
Time limit exceeded |
64 |
Halted |
0 ms |
0 KB |
- |