/**
____ ____ ____ ____ ____ ____
||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 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];
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);
}
}
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;
}
/**
5 2
2
5 1
3 5
1
5 3
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
6 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9640 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
6 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
6 ms |
9684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
6 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9640 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
6 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
6 ms |
9684 KB |
Output is correct |
13 |
Correct |
11 ms |
9812 KB |
Output is correct |
14 |
Correct |
11 ms |
9852 KB |
Output is correct |
15 |
Correct |
5 ms |
9812 KB |
Output is correct |
16 |
Correct |
8 ms |
9812 KB |
Output is correct |
17 |
Correct |
8 ms |
9892 KB |
Output is correct |
18 |
Correct |
11 ms |
9872 KB |
Output is correct |
19 |
Correct |
10 ms |
9896 KB |
Output is correct |
20 |
Correct |
10 ms |
9812 KB |
Output is correct |
21 |
Correct |
7 ms |
9812 KB |
Output is correct |
22 |
Correct |
12 ms |
9812 KB |
Output is correct |
23 |
Correct |
7 ms |
9868 KB |
Output is correct |
24 |
Correct |
8 ms |
9812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
16200 KB |
Output is correct |
2 |
Correct |
44 ms |
16080 KB |
Output is correct |
3 |
Correct |
48 ms |
17156 KB |
Output is correct |
4 |
Correct |
36 ms |
15700 KB |
Output is correct |
5 |
Runtime error |
46 ms |
30548 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2071 ms |
16676 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
42 ms |
29508 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
6 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9640 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
6 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
6 ms |
9684 KB |
Output is correct |
13 |
Correct |
11 ms |
9812 KB |
Output is correct |
14 |
Correct |
11 ms |
9852 KB |
Output is correct |
15 |
Correct |
5 ms |
9812 KB |
Output is correct |
16 |
Correct |
8 ms |
9812 KB |
Output is correct |
17 |
Correct |
8 ms |
9892 KB |
Output is correct |
18 |
Correct |
11 ms |
9872 KB |
Output is correct |
19 |
Correct |
10 ms |
9896 KB |
Output is correct |
20 |
Correct |
10 ms |
9812 KB |
Output is correct |
21 |
Correct |
7 ms |
9812 KB |
Output is correct |
22 |
Correct |
12 ms |
9812 KB |
Output is correct |
23 |
Correct |
7 ms |
9868 KB |
Output is correct |
24 |
Correct |
8 ms |
9812 KB |
Output is correct |
25 |
Correct |
44 ms |
16200 KB |
Output is correct |
26 |
Correct |
44 ms |
16080 KB |
Output is correct |
27 |
Correct |
48 ms |
17156 KB |
Output is correct |
28 |
Correct |
36 ms |
15700 KB |
Output is correct |
29 |
Runtime error |
46 ms |
30548 KB |
Execution killed with signal 11 |
30 |
Halted |
0 ms |
0 KB |
- |