/**
____ ____ ____ ____ ____ ____
||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 = 1e5 + 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 used[maxn];
int par[maxn], lf[maxn], rf[maxn];
int find_leader(int v)
{
if (v == par[v])
return v;
return (par[v] = find_leader(par[v]));
}
void unite(int v, int u)
{
v = find_leader(v);
u = find_leader(u);
par[u] = v;
lf[v] = min(lf[v], lf[u]);
rf[v] = max(rf[v], rf[u]);
}
int nxt[maxn], bef[maxn], us[maxn];
int solve_query(int s, int t)
{
for (int i = 1; i <= n; i ++)
{
used[i] = 0;
par[i] = lf[i] = rf[i] = i;
}
for (int i = 1; i <= m; i ++)
{
us[i] = 0;
nxt[i] = i + 1;
bef[i] = i - 1;
}
queue < int > pq;
used[s] = 1;
lf[s] = s - 1;
rf[s] = s + 1;
pq.push(s);
while(!pq.empty())
{
int cur = pq.front();
pq.pop();
///cout << "cur: " << cur << endl;
int i = 1;
while(i <= m)
{
if (us[i])
{
i = nxt[i];
continue;
}
if (on_train(cur, i))
{
nxt[bef[i]] = nxt[i];
bef[nxt[i]] = bef[i];
us[i] = 1;
if (r[i].a < r[i].b)
{
int j = cur;
while(j <= r[i].b)
{
if (used[j])
{
j = rf[find_leader(j)];
continue;
}
used[j] = used[cur] + 1;
lf[j] = j - 1;
rf[j] = j + 1;
if (used[j - 1])
unite(j, j - 1);
if (used[j + 1])
unite(j, j + 1);
pq.push(j);
j ++;
}
}
else
{
int j = cur;
while(j >= r[i].b)
{
if (used[j])
{
j = lf[find_leader(j)];
continue;
}
used[j] = used[cur] + 1;
lf[j] = j - 1;
rf[j] = j + 1;
if (used[j - 1])
unite(j, j - 1);
if (used[j + 1])
unite(j, j + 1);
pq.push(j);
j --;
}
}
}
i = nxt[i];
}
}
return used[t] - 1;
}
void solve()
{
cin >> n >> k;
cin >> m;
for (int i = 1; i <= m; i ++)
cin >> r[i].a >> r[i].b;
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;
}
/**
5 2
2
5 1
3 5
1
3 2
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
340 KB |
Output is correct |
2 |
Correct |
43 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
27 ms |
340 KB |
Output is correct |
5 |
Correct |
57 ms |
340 KB |
Output is correct |
6 |
Correct |
13 ms |
364 KB |
Output is correct |
7 |
Correct |
15 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
15 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
52 ms |
340 KB |
Output is correct |
12 |
Correct |
6 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
340 KB |
Output is correct |
2 |
Correct |
43 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
27 ms |
340 KB |
Output is correct |
5 |
Correct |
57 ms |
340 KB |
Output is correct |
6 |
Correct |
13 ms |
364 KB |
Output is correct |
7 |
Correct |
15 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
15 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
52 ms |
340 KB |
Output is correct |
12 |
Correct |
6 ms |
340 KB |
Output is correct |
13 |
Execution timed out |
2073 ms |
412 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2069 ms |
3952 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2037 ms |
4180 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
15 ms |
2004 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
340 KB |
Output is correct |
2 |
Correct |
43 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
27 ms |
340 KB |
Output is correct |
5 |
Correct |
57 ms |
340 KB |
Output is correct |
6 |
Correct |
13 ms |
364 KB |
Output is correct |
7 |
Correct |
15 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
15 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
52 ms |
340 KB |
Output is correct |
12 |
Correct |
6 ms |
340 KB |
Output is correct |
13 |
Execution timed out |
2073 ms |
412 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |