/**
____ ____ ____ ____ ____ ____
||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];
void solve()
{
cin >> n >> k;
cin >> m;
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
{
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);
}
}
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]];
}
cin >> q;
for (int i = 1; i <= q; i ++)
{
int s, t;
cin >> s >> t;
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;
}
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));
}
}
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));
}
cin >> q;
for (int i = 1; i <= q; i ++)
{
int s, t;
cin >> s >> t;
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:169:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for (int i = 0; i < rt.size(); i ++)
| ~~^~~~~~~~~~~
Main.cpp:179:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | for (int i = 0; i < lt.size(); i ++)
| ~~^~~~~~~~~~~
Main.cpp:189:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
189 | for (int i = 0; i < frt.size(); i ++)
| ~~^~~~~~~~~~~~
Main.cpp:191:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
191 | while(pt < frt.size() && frt[pt].a <= frt[i].b)
| ~~~^~~~~~~~~~~~
Main.cpp:201:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | for (int i = 0; i < flt.size(); i ++)
| ~~^~~~~~~~~~~~
Main.cpp:203:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
203 | while(pt < flt.size() && flt[pt].a >= flt[i].b)
| ~~~^~~~~~~~~~~~
Main.cpp:213:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
213 | for (int i = 0; i < frt.size(); i ++)
| ~~^~~~~~~~~~~~
Main.cpp:224:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
224 | for (int i = 0; i < flt.size(); i ++)
| ~~^~~~~~~~~~~~
Main.cpp:223:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
223 | for (int j = 1; j < maxlog; j ++)
| ^~~
Main.cpp:234:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
234 | cin >> q;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19140 KB |
Output is correct |
2 |
Correct |
9 ms |
19028 KB |
Output is correct |
3 |
Correct |
10 ms |
19156 KB |
Output is correct |
4 |
Correct |
9 ms |
19152 KB |
Output is correct |
5 |
Correct |
9 ms |
19036 KB |
Output is correct |
6 |
Correct |
9 ms |
19284 KB |
Output is correct |
7 |
Correct |
10 ms |
19096 KB |
Output is correct |
8 |
Correct |
9 ms |
19152 KB |
Output is correct |
9 |
Correct |
10 ms |
19336 KB |
Output is correct |
10 |
Correct |
9 ms |
19224 KB |
Output is correct |
11 |
Correct |
10 ms |
19028 KB |
Output is correct |
12 |
Correct |
10 ms |
19348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19140 KB |
Output is correct |
2 |
Correct |
9 ms |
19028 KB |
Output is correct |
3 |
Correct |
10 ms |
19156 KB |
Output is correct |
4 |
Correct |
9 ms |
19152 KB |
Output is correct |
5 |
Correct |
9 ms |
19036 KB |
Output is correct |
6 |
Correct |
9 ms |
19284 KB |
Output is correct |
7 |
Correct |
10 ms |
19096 KB |
Output is correct |
8 |
Correct |
9 ms |
19152 KB |
Output is correct |
9 |
Correct |
10 ms |
19336 KB |
Output is correct |
10 |
Correct |
9 ms |
19224 KB |
Output is correct |
11 |
Correct |
10 ms |
19028 KB |
Output is correct |
12 |
Correct |
10 ms |
19348 KB |
Output is correct |
13 |
Correct |
15 ms |
19176 KB |
Output is correct |
14 |
Correct |
16 ms |
19156 KB |
Output is correct |
15 |
Correct |
10 ms |
19156 KB |
Output is correct |
16 |
Correct |
13 ms |
19284 KB |
Output is correct |
17 |
Correct |
12 ms |
19284 KB |
Output is correct |
18 |
Correct |
11 ms |
19480 KB |
Output is correct |
19 |
Correct |
14 ms |
19284 KB |
Output is correct |
20 |
Correct |
15 ms |
19276 KB |
Output is correct |
21 |
Correct |
11 ms |
19260 KB |
Output is correct |
22 |
Correct |
11 ms |
19360 KB |
Output is correct |
23 |
Correct |
11 ms |
19156 KB |
Output is correct |
24 |
Correct |
11 ms |
19532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
25556 KB |
Output is correct |
2 |
Correct |
44 ms |
25420 KB |
Output is correct |
3 |
Correct |
54 ms |
26596 KB |
Output is correct |
4 |
Correct |
47 ms |
25180 KB |
Output is correct |
5 |
Correct |
170 ms |
29552 KB |
Output is correct |
6 |
Correct |
122 ms |
33876 KB |
Output is correct |
7 |
Correct |
87 ms |
30604 KB |
Output is correct |
8 |
Correct |
91 ms |
26316 KB |
Output is correct |
9 |
Correct |
48 ms |
24652 KB |
Output is correct |
10 |
Correct |
137 ms |
29464 KB |
Output is correct |
11 |
Correct |
87 ms |
32580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
26536 KB |
Output is correct |
2 |
Correct |
103 ms |
30920 KB |
Output is correct |
3 |
Correct |
83 ms |
35792 KB |
Output is correct |
4 |
Correct |
98 ms |
33012 KB |
Output is correct |
5 |
Correct |
100 ms |
30776 KB |
Output is correct |
6 |
Correct |
96 ms |
31256 KB |
Output is correct |
7 |
Correct |
110 ms |
36152 KB |
Output is correct |
8 |
Correct |
115 ms |
35008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1505 ms |
29652 KB |
Output is correct |
2 |
Execution timed out |
2100 ms |
26988 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19140 KB |
Output is correct |
2 |
Correct |
9 ms |
19028 KB |
Output is correct |
3 |
Correct |
10 ms |
19156 KB |
Output is correct |
4 |
Correct |
9 ms |
19152 KB |
Output is correct |
5 |
Correct |
9 ms |
19036 KB |
Output is correct |
6 |
Correct |
9 ms |
19284 KB |
Output is correct |
7 |
Correct |
10 ms |
19096 KB |
Output is correct |
8 |
Correct |
9 ms |
19152 KB |
Output is correct |
9 |
Correct |
10 ms |
19336 KB |
Output is correct |
10 |
Correct |
9 ms |
19224 KB |
Output is correct |
11 |
Correct |
10 ms |
19028 KB |
Output is correct |
12 |
Correct |
10 ms |
19348 KB |
Output is correct |
13 |
Correct |
15 ms |
19176 KB |
Output is correct |
14 |
Correct |
16 ms |
19156 KB |
Output is correct |
15 |
Correct |
10 ms |
19156 KB |
Output is correct |
16 |
Correct |
13 ms |
19284 KB |
Output is correct |
17 |
Correct |
12 ms |
19284 KB |
Output is correct |
18 |
Correct |
11 ms |
19480 KB |
Output is correct |
19 |
Correct |
14 ms |
19284 KB |
Output is correct |
20 |
Correct |
15 ms |
19276 KB |
Output is correct |
21 |
Correct |
11 ms |
19260 KB |
Output is correct |
22 |
Correct |
11 ms |
19360 KB |
Output is correct |
23 |
Correct |
11 ms |
19156 KB |
Output is correct |
24 |
Correct |
11 ms |
19532 KB |
Output is correct |
25 |
Correct |
45 ms |
25556 KB |
Output is correct |
26 |
Correct |
44 ms |
25420 KB |
Output is correct |
27 |
Correct |
54 ms |
26596 KB |
Output is correct |
28 |
Correct |
47 ms |
25180 KB |
Output is correct |
29 |
Correct |
170 ms |
29552 KB |
Output is correct |
30 |
Correct |
122 ms |
33876 KB |
Output is correct |
31 |
Correct |
87 ms |
30604 KB |
Output is correct |
32 |
Correct |
91 ms |
26316 KB |
Output is correct |
33 |
Correct |
48 ms |
24652 KB |
Output is correct |
34 |
Correct |
137 ms |
29464 KB |
Output is correct |
35 |
Correct |
87 ms |
32580 KB |
Output is correct |
36 |
Correct |
53 ms |
26536 KB |
Output is correct |
37 |
Correct |
103 ms |
30920 KB |
Output is correct |
38 |
Correct |
83 ms |
35792 KB |
Output is correct |
39 |
Correct |
98 ms |
33012 KB |
Output is correct |
40 |
Correct |
100 ms |
30776 KB |
Output is correct |
41 |
Correct |
96 ms |
31256 KB |
Output is correct |
42 |
Correct |
110 ms |
36152 KB |
Output is correct |
43 |
Correct |
115 ms |
35008 KB |
Output is correct |
44 |
Correct |
1505 ms |
29652 KB |
Output is correct |
45 |
Execution timed out |
2100 ms |
26988 KB |
Time limit exceeded |
46 |
Halted |
0 ms |
0 KB |
- |