#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
// #define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
const ll inf = 1ll<<60;
const int iinf=100002;
const ll mod = 1e9+7;
const ll maxn=1e5+5;
const double PI=acos(-1);
ll pw(ll x, ll p, ll m=mod){
ll ret=1;
while (p>0){
if (p&1){
ret*=x;
ret%=m;
}
x*=x;
x%=m;
p>>=1;
}
return ret;
}
ll inv(ll a, ll m=mod){
return pw(a,m-2);
}
//=======================================================================================
pii def = {iinf, 0};
const int mxpw=17;
pii sparsel[mxpw][maxn][mxpw], sparser[mxpw][maxn][mxpw];
int smol[maxn];
int pw2[maxn];
vector<pii> seg(4*maxn);
vector<pii> tag(4*maxn);
void push(int x, int l, int r){
seg[x].f=min(seg[x].f, tag[x].f);
seg[x].s=max(seg[x].s, tag[x].s);
if (l!=r){
tag[x+x].f=min(tag[x].f, tag[x+x].f);
tag[x+x].s=max(tag[x].s, tag[x+x].s);
tag[x+x+1].f=min(tag[x].f, tag[x+x+1].f);
tag[x+x+1].s=max(tag[x].s, tag[x+x+1].s);
}
tag[x]=def;
}
void pull(int x){
seg[x].f=min(seg[x+x].f, seg[x+x+1].f);
seg[x].s=max(seg[x+x].s, seg[x+x+1].s);
}
void build(int l, int r, int x){
if (l==r){
seg[x] = {l, l};
return;
}
int mid = (l+r) >> 1;
build(l, mid, x+x);
build(mid+1, r, x+x+1);
pull(x);
}
void modify(int l, int r, int nl, int nr, int x, pii val){
if (l>nr||r<nl){
push(x, nl, nr);
return;
}
if (l<=nl&&nr<=r){
tag[x].f=min(tag[x].f, val.f);
tag[x].s=max(tag[x].s, val.s);
push(x, nl, nr);
return;
}
push(x, nl, nr);
int mid = (nl+nr) >> 1;
modify(l, r, nl, mid, x+x, val);
modify(l, r, mid+1, nr, x+x+1, val);
pull(x);
}
pii query(int l, int r, int pos, int x){
if (l==r){
push(x, l, r);
return seg[x];
}
push(x, l, r);
int mid = (l+r) >> 1;
if (l<=pos && pos<=mid){
return query(l, mid, pos, x+x);
}
else {
return query(mid+1, r, pos, x+x+1);
}
}
int n, k;
int m, q;
void init(){
REP(i, 4*maxn){
tag[i] = def;
}
build(1, n, 1);
pw2[0]=1;
REP1(i, 18){
pw2[i]=pw2[i-1]*2;
}
REP1(i, n+2){
smol[i]=log2(i);
}
REP(i, mxpw){
REP1(j, n){
REP(k, mxpw){
sparsel[i][j][k]=sparser[i][j][k]={j, j};
}
}
}
}
pii eq(int l, int r){
int tl, tr;
if (l<r){
tl=l;
tr=l+k-1;
if (tr>r) tr=r;
}
else {
tl=l;
tr=l-k+1;
if (tr<r){
tr=r;
}
swap(tl, tr);
}
return {tl, tr};
}
pii rangval(int a, pii cur){
int cd=cur.s-cur.f+1;
pii ret;
ret.s = max(sparsel[a][cur.f][smol[cd]].s, sparser[a][cur.s][smol[cd]].s);
ret.f = min(sparsel[a][cur.f][smol[cd]].f, sparser[a][cur.s][smol[cd]].f);
return ret;
}
void makesparse(){
REP1(i, n){
sparsel[0][i][0] = query(1, n, i, 1);
sparser[0][i][0] = sparsel[0][i][0];
// cout<<sparsel[0][i][0].f<<' '<<sparsel[0][i][0].s<<endl;
}
int tl, tr;
pii ret;
REP(t, mxpw){
if (t!=0){
REP1(i, n){
tl=sparsel[t-1][i][0].f; tr=sparsel[t-1][i][0].s;
ret = rangval(t-1, {tl, tr});
sparsel[t][i][0] = sparser[t][i][0] = ret;
}
}
for (int i=n; i>=1; i--){
REP1(j, mxpw-1){
sparsel[t][i][j].s = max(sparsel[t][i][j-1].s, sparsel[t][min(i+pw2[j-1], n)][j-1].s);
sparsel[t][i][j].f = min(sparsel[t][i][j-1].f, sparsel[t][min(i+pw2[j-1], n)][j-1].f);
}
}
for (int i=1; i<=n; i++){
REP1(j, mxpw-1){
sparser[t][i][j].s = max(sparser[t][i][j-1].s, sparser[t][max(i-pw2[j-1], 1)][j-1].s);
sparser[t][i][j].f = min(sparser[t][i][j-1].f, sparser[t][max(i-pw2[j-1], 1)][j-1].f);
}
}
}
}
void runq(){
pii cur, ret;
REP(i, q){
int l, r; cin>>l>>r;
int res = 0;
if (l<r){
cur = {l, l};
RREP(j, mxpw){
ret = rangval(j, cur);
if (ret.s >= r) continue;
res += pw2[j];
cur = ret;
}
if (res == (1<<mxpw)-1){
res = -1;
}
else res++;
}
else {
cur = {l, l};
RREP(j, mxpw){
ret = rangval(j, cur);
if (ret.f <= r) continue;
res += pw2[j];
cur = ret;
// cout<<i<<' '<<j<<' '<<cur.f<<' '<<cur.s<<endl;
}
if (res == (1<<mxpw)-1){
res = -1;
}
else res++;
}
cout<<res<<endl;
}
}
signed main (){
IOS();
cin>>n>>k;
cin>>m;
init();
REP(i, m){
int l, r; cin>>l>>r;
pii ret = eq(l, r);
// cout<<ret.f<<' '<<ret.s<<endl;
if (l<r){
modify(ret.f, ret.s, 1, n, 1, {iinf, r});
}
else { // r to l
modify(ret.f, ret.s, 1, n, 1, {r, 0});
}
}
makesparse();
cin>>q;
runq();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8148 KB |
Output is correct |
2 |
Correct |
6 ms |
8148 KB |
Output is correct |
3 |
Correct |
5 ms |
8148 KB |
Output is correct |
4 |
Correct |
5 ms |
8204 KB |
Output is correct |
5 |
Correct |
5 ms |
8148 KB |
Output is correct |
6 |
Correct |
6 ms |
8148 KB |
Output is correct |
7 |
Correct |
5 ms |
8128 KB |
Output is correct |
8 |
Correct |
5 ms |
8148 KB |
Output is correct |
9 |
Correct |
5 ms |
8128 KB |
Output is correct |
10 |
Correct |
4 ms |
6868 KB |
Output is correct |
11 |
Correct |
8 ms |
8248 KB |
Output is correct |
12 |
Correct |
6 ms |
8148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8148 KB |
Output is correct |
2 |
Correct |
6 ms |
8148 KB |
Output is correct |
3 |
Correct |
5 ms |
8148 KB |
Output is correct |
4 |
Correct |
5 ms |
8204 KB |
Output is correct |
5 |
Correct |
5 ms |
8148 KB |
Output is correct |
6 |
Correct |
6 ms |
8148 KB |
Output is correct |
7 |
Correct |
5 ms |
8128 KB |
Output is correct |
8 |
Correct |
5 ms |
8148 KB |
Output is correct |
9 |
Correct |
5 ms |
8128 KB |
Output is correct |
10 |
Correct |
4 ms |
6868 KB |
Output is correct |
11 |
Correct |
8 ms |
8248 KB |
Output is correct |
12 |
Correct |
6 ms |
8148 KB |
Output is correct |
13 |
Correct |
17 ms |
15884 KB |
Output is correct |
14 |
Correct |
18 ms |
15944 KB |
Output is correct |
15 |
Correct |
12 ms |
15828 KB |
Output is correct |
16 |
Correct |
17 ms |
15944 KB |
Output is correct |
17 |
Correct |
18 ms |
15956 KB |
Output is correct |
18 |
Correct |
18 ms |
15944 KB |
Output is correct |
19 |
Correct |
17 ms |
15432 KB |
Output is correct |
20 |
Correct |
17 ms |
15948 KB |
Output is correct |
21 |
Correct |
13 ms |
15828 KB |
Output is correct |
22 |
Correct |
18 ms |
15960 KB |
Output is correct |
23 |
Correct |
17 ms |
15944 KB |
Output is correct |
24 |
Correct |
22 ms |
15828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
540 ms |
460364 KB |
Output is correct |
2 |
Correct |
525 ms |
460580 KB |
Output is correct |
3 |
Correct |
543 ms |
460432 KB |
Output is correct |
4 |
Correct |
521 ms |
460276 KB |
Output is correct |
5 |
Correct |
724 ms |
461748 KB |
Output is correct |
6 |
Correct |
637 ms |
461772 KB |
Output is correct |
7 |
Correct |
614 ms |
461460 KB |
Output is correct |
8 |
Correct |
604 ms |
456140 KB |
Output is correct |
9 |
Correct |
594 ms |
460580 KB |
Output is correct |
10 |
Correct |
658 ms |
461708 KB |
Output is correct |
11 |
Correct |
641 ms |
461644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
684 ms |
461040 KB |
Output is correct |
2 |
Correct |
777 ms |
462368 KB |
Output is correct |
3 |
Correct |
696 ms |
461244 KB |
Output is correct |
4 |
Correct |
743 ms |
461968 KB |
Output is correct |
5 |
Correct |
793 ms |
457828 KB |
Output is correct |
6 |
Correct |
792 ms |
462280 KB |
Output is correct |
7 |
Correct |
824 ms |
462348 KB |
Output is correct |
8 |
Correct |
814 ms |
462376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
901 ms |
462496 KB |
Output is correct |
2 |
Correct |
763 ms |
461444 KB |
Output is correct |
3 |
Correct |
827 ms |
460808 KB |
Output is correct |
4 |
Correct |
624 ms |
460492 KB |
Output is correct |
5 |
Correct |
633 ms |
460116 KB |
Output is correct |
6 |
Correct |
565 ms |
460108 KB |
Output is correct |
7 |
Correct |
666 ms |
461232 KB |
Output is correct |
8 |
Correct |
5 ms |
8148 KB |
Output is correct |
9 |
Correct |
17 ms |
15948 KB |
Output is correct |
10 |
Correct |
712 ms |
461844 KB |
Output is correct |
11 |
Correct |
801 ms |
462224 KB |
Output is correct |
12 |
Correct |
815 ms |
457852 KB |
Output is correct |
13 |
Correct |
828 ms |
462220 KB |
Output is correct |
14 |
Correct |
5 ms |
8148 KB |
Output is correct |
15 |
Correct |
19 ms |
15944 KB |
Output is correct |
16 |
Correct |
677 ms |
461836 KB |
Output is correct |
17 |
Correct |
826 ms |
462484 KB |
Output is correct |
18 |
Correct |
826 ms |
462352 KB |
Output is correct |
19 |
Correct |
779 ms |
462412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8148 KB |
Output is correct |
2 |
Correct |
6 ms |
8148 KB |
Output is correct |
3 |
Correct |
5 ms |
8148 KB |
Output is correct |
4 |
Correct |
5 ms |
8204 KB |
Output is correct |
5 |
Correct |
5 ms |
8148 KB |
Output is correct |
6 |
Correct |
6 ms |
8148 KB |
Output is correct |
7 |
Correct |
5 ms |
8128 KB |
Output is correct |
8 |
Correct |
5 ms |
8148 KB |
Output is correct |
9 |
Correct |
5 ms |
8128 KB |
Output is correct |
10 |
Correct |
4 ms |
6868 KB |
Output is correct |
11 |
Correct |
8 ms |
8248 KB |
Output is correct |
12 |
Correct |
6 ms |
8148 KB |
Output is correct |
13 |
Correct |
17 ms |
15884 KB |
Output is correct |
14 |
Correct |
18 ms |
15944 KB |
Output is correct |
15 |
Correct |
12 ms |
15828 KB |
Output is correct |
16 |
Correct |
17 ms |
15944 KB |
Output is correct |
17 |
Correct |
18 ms |
15956 KB |
Output is correct |
18 |
Correct |
18 ms |
15944 KB |
Output is correct |
19 |
Correct |
17 ms |
15432 KB |
Output is correct |
20 |
Correct |
17 ms |
15948 KB |
Output is correct |
21 |
Correct |
13 ms |
15828 KB |
Output is correct |
22 |
Correct |
18 ms |
15960 KB |
Output is correct |
23 |
Correct |
17 ms |
15944 KB |
Output is correct |
24 |
Correct |
22 ms |
15828 KB |
Output is correct |
25 |
Correct |
540 ms |
460364 KB |
Output is correct |
26 |
Correct |
525 ms |
460580 KB |
Output is correct |
27 |
Correct |
543 ms |
460432 KB |
Output is correct |
28 |
Correct |
521 ms |
460276 KB |
Output is correct |
29 |
Correct |
724 ms |
461748 KB |
Output is correct |
30 |
Correct |
637 ms |
461772 KB |
Output is correct |
31 |
Correct |
614 ms |
461460 KB |
Output is correct |
32 |
Correct |
604 ms |
456140 KB |
Output is correct |
33 |
Correct |
594 ms |
460580 KB |
Output is correct |
34 |
Correct |
658 ms |
461708 KB |
Output is correct |
35 |
Correct |
641 ms |
461644 KB |
Output is correct |
36 |
Correct |
684 ms |
461040 KB |
Output is correct |
37 |
Correct |
777 ms |
462368 KB |
Output is correct |
38 |
Correct |
696 ms |
461244 KB |
Output is correct |
39 |
Correct |
743 ms |
461968 KB |
Output is correct |
40 |
Correct |
793 ms |
457828 KB |
Output is correct |
41 |
Correct |
792 ms |
462280 KB |
Output is correct |
42 |
Correct |
824 ms |
462348 KB |
Output is correct |
43 |
Correct |
814 ms |
462376 KB |
Output is correct |
44 |
Correct |
901 ms |
462496 KB |
Output is correct |
45 |
Correct |
763 ms |
461444 KB |
Output is correct |
46 |
Correct |
827 ms |
460808 KB |
Output is correct |
47 |
Correct |
624 ms |
460492 KB |
Output is correct |
48 |
Correct |
633 ms |
460116 KB |
Output is correct |
49 |
Correct |
565 ms |
460108 KB |
Output is correct |
50 |
Correct |
666 ms |
461232 KB |
Output is correct |
51 |
Correct |
5 ms |
8148 KB |
Output is correct |
52 |
Correct |
17 ms |
15948 KB |
Output is correct |
53 |
Correct |
712 ms |
461844 KB |
Output is correct |
54 |
Correct |
801 ms |
462224 KB |
Output is correct |
55 |
Correct |
815 ms |
457852 KB |
Output is correct |
56 |
Correct |
828 ms |
462220 KB |
Output is correct |
57 |
Correct |
5 ms |
8148 KB |
Output is correct |
58 |
Correct |
19 ms |
15944 KB |
Output is correct |
59 |
Correct |
677 ms |
461836 KB |
Output is correct |
60 |
Correct |
826 ms |
462484 KB |
Output is correct |
61 |
Correct |
826 ms |
462352 KB |
Output is correct |
62 |
Correct |
779 ms |
462412 KB |
Output is correct |
63 |
Correct |
693 ms |
461096 KB |
Output is correct |
64 |
Correct |
736 ms |
461296 KB |
Output is correct |
65 |
Correct |
747 ms |
461044 KB |
Output is correct |
66 |
Correct |
823 ms |
462472 KB |
Output is correct |
67 |
Correct |
809 ms |
462484 KB |
Output is correct |
68 |
Correct |
814 ms |
457936 KB |
Output is correct |
69 |
Correct |
842 ms |
462352 KB |
Output is correct |
70 |
Correct |
785 ms |
462408 KB |
Output is correct |
71 |
Correct |
831 ms |
462472 KB |
Output is correct |