/*
weak weak we ak we akwea weak we
weak weak we ak weak weak we ak we
weakweak we ak wea ak we akwe
wea we ak we ak we akwe
wea we ak we ak we akwe
wea eak weak we ak we ak we
wea wea ak we ak weak we
we
we ak wea ak weak we
we ak wea weak wea eak we
we ak we ak wea wea we we
weak we ak we we we we
we we ak we we we we
we wea weak wea wea weak weak
weak wea akw weak weak
*/
//#define _GLIBCXX_DEBUG //is only used when couldn't find bug
using namespace std;
#pragma GCC optimize ("Ofast")
//headers
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <utility>
#include <bitset>
#include <set>
#include <string>
#include <stack>
#include <iomanip>
#include <map>
#include <memory.h>
#include <deque>
#include <time.h>
#include <assert.h>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
//defines
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<LL>> vvl;
#define pb push_back
#define F first
#define S second
#define mid (LB+RB)/2
#define mkp make_pair
//iterators
#define iter(x) x.begin(),x.end()
#define aiter(a,n) a,a+n
//loops
#define REP(n) for (int ___=n > 0 ? n : 0;___--;)
#define REP0(i,n) for (int i=0,___=n;i<___;++i)
#define REP1(i,n) for (int i=1,___=n;i<=___;++i)
#define MEM(e,val) memset (e,val,sizeof(e))
/*
When he said Super Idol??摰寥瘝∩????急?甇????瘝∩???潛??105 簞C??皛湔輕皜滲?擐偌雿??乩????舐頝?隡蝚???韏瑚?隞?賭?頧餉?憭梯揖撖寞╪?喟??抒?銝?港??暹敺?敹?敶?撖寞?霂港?????曄?霈拇??亙??Z蕭?芸楛?╪?喲???芋??
I really felt that.
every one is so dian except me
still too weak ?拙?
*/
//IO
#include <cstdio>
#include <iostream>
#include <fstream>
#define want_to_be_more_dian ios_base::sync_with_stdio(false),cin.tie(0);
//pbds
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
//tree <pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>;
*/
//constants
#include <climits>
const int maxn = 1e5+10,mod = 0;
const long long inf = 0;
const double eps = 0;
//workspace
struct segmenttree{
pii val[maxn*4], arr[maxn];
pii pull(pii l, pii r){
return mkp(min(l.F, r.F), max(l.S, r.S));
}
void maketree(int cur, int LB, int RB){
if (LB == RB) val[cur] = arr[LB];
else{
int m = (LB + RB) / 2;
maketree(cur*2, LB, m);
maketree(cur*2+1, m+1, RB);
val[cur] = pull(val[cur*2], val[cur*2+1]);
}
}
pii query(int l, int r, int cur, int LB, int RB){
if (l == LB and r == RB) return val[cur];
int m = (LB + RB) / 2;
if (r <= m) return query(l, r, cur*2, LB, m);
else if (l > m) return query(l, r, cur*2+1, m+1, RB);
else return pull(query(l, m, cur*2, LB, m), query(m+1, r, cur*2+1, m+1, RB));
}
}seg[17];
int mx[maxn], mn[maxn];
inline void solve(){
int n, k, m, q;
cin >> n >> k >> m;
REP1(i, n) mx[i] = mn[i] = i;
REP(m){
int a, b;
cin >> a >> b;
mx[a] = max(mx[a], b);
mn[a] = min(mn[a], b);
}
deque <pii> dq;
REP1(i, n){
while (!dq.empty() and mx[i] > dq.back().F) dq.pop_back();
dq.pb(mkp(mx[i], i));
if (dq.front().S + k <= i) dq.pop_front();
mx[i] = dq.front().F;
}
while (!dq.empty()) dq.pop_back();
for (int i=n;i;--i){
while (!dq.empty() and mn[i] < dq.back().F) dq.pop_back();
dq.pb(mkp(mn[i], i));
if (dq.front().S - k >= i) dq.pop_front();
mn[i] = dq.front().F;
}
REP1(i, n) seg[0].arr[i] = mkp(mn[i], mx[i]);
seg[0].maketree(1, 1, n);
REP1(i, 16){
REP1(j, n) seg[i].arr[j] = seg[i-1].query(seg[i-1].arr[j].F, seg[i-1].arr[j].S, 1, 1, n);
seg[i].maketree(1, 1, n);
}
cin >> q;
REP(q){
int b, ans = 0;
pii a;
cin >> a.F >> b; a.S = a.F;
for (int i=16;i>=0;--i){
pii s = seg[i].query(a.F, a.S, 1, 1, n);
if (b < s.F or b > s.S){
a = s;
ans |= 1 << i;
}
}
a = seg[0].query(a.F, a.S, 1, 1, n);
if (b >= a.F and b <= a.S) cout << ans + 1 << '\n';
else cout << "-1\n";
}
}
signed main(){
want_to_be_more_dian
//int t,i=1; for (int ;cin;)//use in multi-testcases and end in EOF problems
//int t,i=1; for (cin >> t;i<=t;++i)//use in multi-testcases problems
//cout << "Case #" << i << ": ",//use in Google, FB competitions
solve();//always used
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
716 KB |
Output is correct |
2 |
Correct |
1 ms |
716 KB |
Output is correct |
3 |
Correct |
1 ms |
704 KB |
Output is correct |
4 |
Correct |
1 ms |
708 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
1 ms |
716 KB |
Output is correct |
7 |
Correct |
1 ms |
716 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
716 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
716 KB |
Output is correct |
12 |
Correct |
1 ms |
708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
716 KB |
Output is correct |
2 |
Correct |
1 ms |
716 KB |
Output is correct |
3 |
Correct |
1 ms |
704 KB |
Output is correct |
4 |
Correct |
1 ms |
708 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
1 ms |
716 KB |
Output is correct |
7 |
Correct |
1 ms |
716 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
716 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
716 KB |
Output is correct |
12 |
Correct |
1 ms |
708 KB |
Output is correct |
13 |
Correct |
6 ms |
1360 KB |
Output is correct |
14 |
Correct |
5 ms |
1348 KB |
Output is correct |
15 |
Correct |
3 ms |
1356 KB |
Output is correct |
16 |
Correct |
3 ms |
1356 KB |
Output is correct |
17 |
Correct |
6 ms |
1352 KB |
Output is correct |
18 |
Correct |
2 ms |
1356 KB |
Output is correct |
19 |
Correct |
6 ms |
1356 KB |
Output is correct |
20 |
Correct |
3 ms |
1416 KB |
Output is correct |
21 |
Correct |
2 ms |
1392 KB |
Output is correct |
22 |
Correct |
4 ms |
1356 KB |
Output is correct |
23 |
Correct |
5 ms |
1356 KB |
Output is correct |
24 |
Correct |
5 ms |
1356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
221 ms |
50300 KB |
Output is correct |
2 |
Correct |
211 ms |
50252 KB |
Output is correct |
3 |
Correct |
239 ms |
50500 KB |
Output is correct |
4 |
Correct |
193 ms |
50108 KB |
Output is correct |
5 |
Correct |
70 ms |
51524 KB |
Output is correct |
6 |
Correct |
200 ms |
51540 KB |
Output is correct |
7 |
Correct |
62 ms |
52072 KB |
Output is correct |
8 |
Correct |
53 ms |
50420 KB |
Output is correct |
9 |
Correct |
51 ms |
50372 KB |
Output is correct |
10 |
Correct |
174 ms |
51484 KB |
Output is correct |
11 |
Correct |
163 ms |
51816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
270 ms |
51140 KB |
Output is correct |
2 |
Correct |
247 ms |
52280 KB |
Output is correct |
3 |
Correct |
380 ms |
51124 KB |
Output is correct |
4 |
Correct |
125 ms |
51528 KB |
Output is correct |
5 |
Correct |
129 ms |
49804 KB |
Output is correct |
6 |
Correct |
124 ms |
49608 KB |
Output is correct |
7 |
Correct |
275 ms |
49628 KB |
Output is correct |
8 |
Correct |
281 ms |
49752 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
288 ms |
49456 KB |
Output is correct |
2 |
Correct |
449 ms |
49912 KB |
Output is correct |
3 |
Correct |
421 ms |
49628 KB |
Output is correct |
4 |
Correct |
390 ms |
49768 KB |
Output is correct |
5 |
Correct |
319 ms |
49892 KB |
Output is correct |
6 |
Correct |
308 ms |
49500 KB |
Output is correct |
7 |
Correct |
200 ms |
50244 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
4 ms |
1356 KB |
Output is correct |
10 |
Correct |
154 ms |
49576 KB |
Output is correct |
11 |
Correct |
202 ms |
49520 KB |
Output is correct |
12 |
Correct |
206 ms |
49600 KB |
Output is correct |
13 |
Correct |
213 ms |
49692 KB |
Output is correct |
14 |
Correct |
1 ms |
716 KB |
Output is correct |
15 |
Correct |
6 ms |
1356 KB |
Output is correct |
16 |
Correct |
199 ms |
49444 KB |
Output is correct |
17 |
Correct |
405 ms |
49720 KB |
Output is correct |
18 |
Correct |
369 ms |
49644 KB |
Output is correct |
19 |
Correct |
338 ms |
49844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
716 KB |
Output is correct |
2 |
Correct |
1 ms |
716 KB |
Output is correct |
3 |
Correct |
1 ms |
704 KB |
Output is correct |
4 |
Correct |
1 ms |
708 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
1 ms |
716 KB |
Output is correct |
7 |
Correct |
1 ms |
716 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
716 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
716 KB |
Output is correct |
12 |
Correct |
1 ms |
708 KB |
Output is correct |
13 |
Correct |
6 ms |
1360 KB |
Output is correct |
14 |
Correct |
5 ms |
1348 KB |
Output is correct |
15 |
Correct |
3 ms |
1356 KB |
Output is correct |
16 |
Correct |
3 ms |
1356 KB |
Output is correct |
17 |
Correct |
6 ms |
1352 KB |
Output is correct |
18 |
Correct |
2 ms |
1356 KB |
Output is correct |
19 |
Correct |
6 ms |
1356 KB |
Output is correct |
20 |
Correct |
3 ms |
1416 KB |
Output is correct |
21 |
Correct |
2 ms |
1392 KB |
Output is correct |
22 |
Correct |
4 ms |
1356 KB |
Output is correct |
23 |
Correct |
5 ms |
1356 KB |
Output is correct |
24 |
Correct |
5 ms |
1356 KB |
Output is correct |
25 |
Correct |
221 ms |
50300 KB |
Output is correct |
26 |
Correct |
211 ms |
50252 KB |
Output is correct |
27 |
Correct |
239 ms |
50500 KB |
Output is correct |
28 |
Correct |
193 ms |
50108 KB |
Output is correct |
29 |
Correct |
70 ms |
51524 KB |
Output is correct |
30 |
Correct |
200 ms |
51540 KB |
Output is correct |
31 |
Correct |
62 ms |
52072 KB |
Output is correct |
32 |
Correct |
53 ms |
50420 KB |
Output is correct |
33 |
Correct |
51 ms |
50372 KB |
Output is correct |
34 |
Correct |
174 ms |
51484 KB |
Output is correct |
35 |
Correct |
163 ms |
51816 KB |
Output is correct |
36 |
Correct |
270 ms |
51140 KB |
Output is correct |
37 |
Correct |
247 ms |
52280 KB |
Output is correct |
38 |
Correct |
380 ms |
51124 KB |
Output is correct |
39 |
Correct |
125 ms |
51528 KB |
Output is correct |
40 |
Correct |
129 ms |
49804 KB |
Output is correct |
41 |
Correct |
124 ms |
49608 KB |
Output is correct |
42 |
Correct |
275 ms |
49628 KB |
Output is correct |
43 |
Correct |
281 ms |
49752 KB |
Output is correct |
44 |
Correct |
288 ms |
49456 KB |
Output is correct |
45 |
Correct |
449 ms |
49912 KB |
Output is correct |
46 |
Correct |
421 ms |
49628 KB |
Output is correct |
47 |
Correct |
390 ms |
49768 KB |
Output is correct |
48 |
Correct |
319 ms |
49892 KB |
Output is correct |
49 |
Correct |
308 ms |
49500 KB |
Output is correct |
50 |
Correct |
200 ms |
50244 KB |
Output is correct |
51 |
Correct |
1 ms |
716 KB |
Output is correct |
52 |
Correct |
4 ms |
1356 KB |
Output is correct |
53 |
Correct |
154 ms |
49576 KB |
Output is correct |
54 |
Correct |
202 ms |
49520 KB |
Output is correct |
55 |
Correct |
206 ms |
49600 KB |
Output is correct |
56 |
Correct |
213 ms |
49692 KB |
Output is correct |
57 |
Correct |
1 ms |
716 KB |
Output is correct |
58 |
Correct |
6 ms |
1356 KB |
Output is correct |
59 |
Correct |
199 ms |
49444 KB |
Output is correct |
60 |
Correct |
405 ms |
49720 KB |
Output is correct |
61 |
Correct |
369 ms |
49644 KB |
Output is correct |
62 |
Correct |
338 ms |
49844 KB |
Output is correct |
63 |
Correct |
379 ms |
49644 KB |
Output is correct |
64 |
Correct |
477 ms |
49668 KB |
Output is correct |
65 |
Correct |
401 ms |
49856 KB |
Output is correct |
66 |
Correct |
94 ms |
49936 KB |
Output is correct |
67 |
Correct |
363 ms |
49668 KB |
Output is correct |
68 |
Correct |
292 ms |
49428 KB |
Output is correct |
69 |
Correct |
116 ms |
49496 KB |
Output is correct |
70 |
Correct |
339 ms |
49524 KB |
Output is correct |
71 |
Correct |
370 ms |
49600 KB |
Output is correct |