#include <bits/stdc++.h>
using namespace std;
const int maxn = 100001,maxlogn = 17;
const int sqr = 18;
int st[4][maxlogn][maxn];
int maxst[maxn];
int l[maxn];
int r[maxn];
int MIN1(int l,int r)
{
int ts = maxst[r-l+1];
return min(st[0][ts][l],st[0][ts][r-(1<<ts)+1]);
}
int MAX1(int l,int r)
{
int ts = maxst[r-l+1];
return max(st[1][ts][l],st[1][ts][r-(1<<ts)+1]);
}
int MINs(int l,int r)
{
int ts = maxst[r-l+1];
return min(st[2][ts][l],st[2][ts][r-(1<<ts)+1]);
}
int MAXs(int l,int r)
{
int ts = maxst[r-l+1];
return max(st[3][ts][l],st[3][ts][r-(1<<ts)+1]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin >> n >> k;
int m;
cin >> m;
vector<int> tl(n),tr(n);
for(int i = 0;i < n;++i)
{
tl[i] = i;
tr[i] = i;
}
for(int i = 0;i < m;++i)
{
int lx,rx;
cin >> lx >> rx;
lx--;
rx--;
if(lx > rx)
{
tl[lx] = min(tl[lx],rx);
}
else
{
tr[lx] = max(tr[lx],rx);
}
}
multiset<int> cc;
for(int i = n-1;i >= 0;--i)
{
if(i+k < n)
{
cc.erase(cc.find(tl[i+k]));
}
// cout << tl[i] << ' ';
cc.insert(tl[i]);
l[i] = *cc.begin();
// cout << l[i] << ' ';
}
// cout << "\n";
cc.clear();
for(int i = 0;i < n;++i)
{
if(i >= k)
{
cc.erase(cc.find(-tr[i-k]));
}
cc.insert(-tr[i]);
r[i] = -(*cc.begin());
// cout << r[i] << ' ';
}
// cout << "\n";
int tst = 0;
for(int j = 1;j < maxn;++j)
{
maxst[j] = tst;
if((1<<(tst+1)) <= j+1)
tst++;
}
for(int i = 0;i < maxlogn;++i)
{
for(int j = 0;j < n-(1<<i)+1;++j)
{
if(i == 0)
st[0][i][j] = l[j];
else
st[0][i][j] = min(st[0][i-1][j],st[0][i-1][j+(1<<(i-1))]);
}
}
for(int i = 0;i < maxlogn;++i)
{
for(int j = 0;j < n-(1<<i)+1;++j)
{
if(i == 0)
st[1][i][j] = r[j];
else
st[1][i][j] = max(st[1][i-1][j],st[1][i-1][j+(1<<(i-1))]);
}
}
for(int i = 0;i < sqr-1;++i)
{
for(int j = 0;j < n;++j)
{
int nl = MIN1(l[j],r[j]);
int nr = MAX1(l[j],r[j]);
l[j] = nl;
r[j] = nr;
}
}
for(int i = 0;i < maxlogn;++i)
{
for(int j = 0;j < n-(1<<i)+1;++j)
{
if(i == 0)
st[2][i][j] = l[j];
else
st[2][i][j] = min(st[2][i-1][j],st[2][i-1][j+(1<<(i-1))]);
}
}
for(int i = 0;i < maxlogn;++i)
{
for(int j = 0;j < n-(1<<i)+1;++j)
{
if(i == 0)
st[3][i][j] = r[j];
else
st[3][i][j] = max(st[3][i-1][j],st[1][i-1][j+(1<<(i-1))]);
}
}
// cout << MIN1(1,1);
int q;
cin >> q;
while(q--)
{
int s,t;
cin >> s >> t;
s--;
t--;
int ls = s,rs = s;
int ans = 0;
int y = 0;
for(int j = 0;j < sqr;++j)
{
int nls = MINs(ls,rs);
int nrs = MAXs(ls,rs);
if(nls > t || nrs < t)
{
ls = nls;
rs = nrs;
ans += sqr;
}
else
{
y= 1;
break;
}
}
for(int j = 0;j < sqr;++j)
{
int nls = MIN1(ls,rs);
int nrs = MAX1(ls,rs);
if(nls > t || nrs < t)
{
ls = nls;
rs = nrs;
ans ++;
}
else
{
ans ++;
y = 1;
break;
}
}
if(!y)
cout << -1 << "\n";
else
cout << ans << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
28508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
33280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
29664 KB |
Output is correct |
| 2 |
Incorrect |
54 ms |
28500 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
