#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<string>
using namespace std;
const int64_t INF = (int64_t) 4 * 1e5 + 5;
const int64_t mINF = 18;
const int64_t MOD = (int64_t) 1e9 + 7;
const int nbit = 11;
const int ndig = 10;
const int nchar = 26;
const int p1 = 31;
const int p2 = 53;
const int D = 4;
int dr[D] = {0, 1, 0, -1};
int dc[D] = {1, 0, -1, 0};
// 0 right // 1 down // 2 left // 3 up
struct Solution
{
int n;
int k;
int m;
int sz;
int LOG;
vector<vector<int> > a;
vector<vector<int> > b;
vector<vector<int> > treer;
vector<vector<int> > treel;
vector<vector<pair<int, int> > > range;
Solution() {}
void solve()
{
cin >> n >> k >> m;
a.resize(n);
b.resize(n);
for(int i = 0; i < m; i++)
{
int u;
int v;
cin >> u >> v;
u--; v--;
if(u < v) a[u].push_back(v);
else b[u].push_back(v);
}
buildTree();
int q;
cin >> q;
for(int i = 0; i < q; i++)
{
int s;
int t;
cin >> s >> t;
s--; t--;
int l = 1;
int r = n;
int ans = -1;
while(l <= r)
{
int mid = l + (r - l) / 2;
if(check(mid, s, t))
{
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans << "\n";
}
}
bool check(int dis, int& s, int& t)
{
int l = s;
int r = s;
while(dis != 0)
{
int bt = 31 - __builtin_clz(dis);
int newl = get(1, 0, sz - 1, l, r, bt, 0);
int newr = get(1, 0, sz - 1, l, r, bt, 1);
l = newl;
r = newr;
dis ^= MASK(bt);
}
return (l <= t && t <= r);
}
void buildTree()
{
sz = n;
LOG = 0;
while(MASK(LOG) <= n) LOG++;
while(__builtin_popcount(sz) != 1) sz++;
treer.resize(LOG, vector<int>(sz * 2, -1));
treel.resize(LOG, vector<int>(sz * 2, n));
range.resize(LOG, vector<pair<int, int> >(n, make_pair(-1, -1)));
for(int i = 0; i < n; i++)
{
range[0][i] = make_pair(i, i);
}
deque<pair<int, int> > dq;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < (int) a[i].size(); j++)
{
int v = a[i][j];
while(!dq.empty() && dq.back().second <= v) dq.pop_back();
dq.push_back(make_pair(i, v));
}
while(!dq.empty() && (dq.front().first + k - 1 < i || dq.front().second < i)) dq.pop_front();
if(dq.empty()) continue;
range[0][i].second = dq.front().second;
}
deque<pair<int, int> > dq2;
for(int i = n - 1; i >= 0; i--)
{
for(int j = 0; j < (int) b[i].size(); j++)
{
int v = b[i][j];
while(!dq2.empty() && dq2.back().second >= v) dq2.pop_back();
dq2.push_back(make_pair(i, v));
}
while(!dq2.empty() && (dq2.front().first - k + 1 > i || dq2.front().second > i)) dq2.pop_front();
if(dq2.empty()) continue;
range[0][i].first = dq2.front().second;
}
for(int i = 0; i < n; i++)
{
treel[0][sz + i] = range[0][i].first;
treer[0][sz + i] = range[0][i].second;
}
for(int i = sz - 1; i >= 1; i--)
{
treer[0][i] = max(treer[0][i * 2], treer[0][i * 2 + 1]);
treel[0][i] = min(treel[0][i * 2], treel[0][i * 2 + 1]);
}
for(int i = 1; i < LOG; i++)
{
// cerr << "i = " << i << "\n";
int prev = i - 1;
for(int j = 0; j < n; j++)
{
int l = range[i - 1][j].first;
int r = range[i - 1][j].second;
int newl = get(1, 0, sz - 1, l, r, prev, 0);
int newr = get(1, 0, sz - 1, l, r, prev, 1);
// cerr << "l = " << l << " ; r = " << r << "\n";
// cerr << "newl = " << newl << " ; newr = " << newr << "\n";
update(j, i, newl, 0);
update(j, i, newr, 1);
range[i][j] = make_pair(newl, newr);
}
// cerr << "\n";
}
}
void update(int& id, int& d, int& val, int t)
{
if(t == 0) treel[d][sz + id] = min(treel[d][sz + id], val);
else treer[d][sz + id] = max(treer[d][sz + id], val);
for(int i = (sz + id) / 2; i >= 1; i /= 2)
{
if(t == 0) treel[d][i] = min(treel[d][i * 2], treel[d][i * 2 + 1]);
else treer[d][i] = max(treer[d][i * 2], treer[d][i * 2 + 1]);
}
}
int get(int node, int nleft, int nright, int& left, int& right, int& d, int t)
{
if(left <= nleft && nright <= right)
{
if(t == 0) return treel[d][node];
return treer[d][node];
}
if(nleft > right || nright < left)
{
if(t == 0) return n;
return -1;
}
int mid = nleft + (nright - nleft) / 2;
int t1 = get(node * 2, nleft, mid, left, right, d, t);
int t2 = get(node * 2 + 1, mid + 1, nright, left, right, d, t);
if(t == 0) return min(t1, t2);
return max(t1, t2);
}
int modsub(int t1, int t2)
{
int res = t1 - t2;
if(res < 0) res += MOD;
return res;
}
int modadd(int t1, int t2)
{
int res = t1 + t2;
if(res >= MOD) res -= MOD;
return res;
}
int modmul(int t1, int t2)
{
int64_t res = 1LL * t1 * t2;
return (res % MOD);
}
bool BIT(int& mask, int& j)
{
return (mask & MASK(j));
}
int64_t MASK(int64_t j)
{
return (1LL << j);
}
};
void __startup()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
}
int main()
{
__startup();
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
Solution().solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
3 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
440 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
3 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
440 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
36 ms |
980 KB |
Output is correct |
14 |
Correct |
32 ms |
980 KB |
Output is correct |
15 |
Correct |
7 ms |
996 KB |
Output is correct |
16 |
Correct |
27 ms |
1000 KB |
Output is correct |
17 |
Correct |
33 ms |
980 KB |
Output is correct |
18 |
Correct |
14 ms |
1016 KB |
Output is correct |
19 |
Correct |
21 ms |
992 KB |
Output is correct |
20 |
Correct |
12 ms |
980 KB |
Output is correct |
21 |
Correct |
4 ms |
980 KB |
Output is correct |
22 |
Correct |
23 ms |
980 KB |
Output is correct |
23 |
Correct |
20 ms |
1004 KB |
Output is correct |
24 |
Correct |
28 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
795 ms |
56844 KB |
Output is correct |
2 |
Correct |
775 ms |
56716 KB |
Output is correct |
3 |
Correct |
840 ms |
57308 KB |
Output is correct |
4 |
Correct |
746 ms |
56548 KB |
Output is correct |
5 |
Correct |
569 ms |
57800 KB |
Output is correct |
6 |
Correct |
751 ms |
60448 KB |
Output is correct |
7 |
Correct |
424 ms |
60488 KB |
Output is correct |
8 |
Correct |
471 ms |
56420 KB |
Output is correct |
9 |
Correct |
419 ms |
56568 KB |
Output is correct |
10 |
Correct |
729 ms |
58296 KB |
Output is correct |
11 |
Correct |
659 ms |
58288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1912 ms |
57136 KB |
Output is correct |
2 |
Execution timed out |
2086 ms |
57928 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2093 ms |
56880 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
3 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
440 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
36 ms |
980 KB |
Output is correct |
14 |
Correct |
32 ms |
980 KB |
Output is correct |
15 |
Correct |
7 ms |
996 KB |
Output is correct |
16 |
Correct |
27 ms |
1000 KB |
Output is correct |
17 |
Correct |
33 ms |
980 KB |
Output is correct |
18 |
Correct |
14 ms |
1016 KB |
Output is correct |
19 |
Correct |
21 ms |
992 KB |
Output is correct |
20 |
Correct |
12 ms |
980 KB |
Output is correct |
21 |
Correct |
4 ms |
980 KB |
Output is correct |
22 |
Correct |
23 ms |
980 KB |
Output is correct |
23 |
Correct |
20 ms |
1004 KB |
Output is correct |
24 |
Correct |
28 ms |
980 KB |
Output is correct |
25 |
Correct |
795 ms |
56844 KB |
Output is correct |
26 |
Correct |
775 ms |
56716 KB |
Output is correct |
27 |
Correct |
840 ms |
57308 KB |
Output is correct |
28 |
Correct |
746 ms |
56548 KB |
Output is correct |
29 |
Correct |
569 ms |
57800 KB |
Output is correct |
30 |
Correct |
751 ms |
60448 KB |
Output is correct |
31 |
Correct |
424 ms |
60488 KB |
Output is correct |
32 |
Correct |
471 ms |
56420 KB |
Output is correct |
33 |
Correct |
419 ms |
56568 KB |
Output is correct |
34 |
Correct |
729 ms |
58296 KB |
Output is correct |
35 |
Correct |
659 ms |
58288 KB |
Output is correct |
36 |
Correct |
1912 ms |
57136 KB |
Output is correct |
37 |
Execution timed out |
2086 ms |
57928 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |