이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
if(x<y)
{
x=y;
return 1;
}
return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
if(x>y)
{
x=y;
return 1;
}
return 0;
}
void online()
{
std::ios_base::sync_with_stdio(0);
cin.tie(0);
}
const ll N=2e5+10,M=998244353;
struct Range
{
ll l,r;
Range(ll _l=0,ll _r=00)
{
l=_l;
r=_r;
}
Range operator |=(const Range &o)
{
minimize(l,o.l);
maximize(r,o.r);
return *this;
}
Range operator |(const Range &o)
{
Range res=*this;
minimize(res.l,o.l);
maximize(res.r,o.r);
return res;
}
};
struct SegmentTree
{
vector<Range> Tree;
vector<Range> Lazy;
ll n;
void build(ll i,ll l,ll r)
{
Lazy[i].l=n;
Lazy[i].r=1;
if(l==r)
{
Tree[i].l=Tree[i].r=l;
return;
}
build(i*2,l,(l+r)/2);
build(i*2+1,(l+r)/2+1,r);
Tree[i].l=min(Tree[i*2].l,Tree[i*2+1].l);
Tree[i].r=max(Tree[i*2].r,Tree[i*2+1].r);
}
SegmentTree(ll _n=0)
{
n=_n;
Tree.resize(4*n);
Lazy.resize(4*n);
if(n!=0)
build(1,1,n);
}
void down(ll i,ll l,ll r)
{
ll x=Lazy[i].l;
Lazy[i].l=n;
if(x!=n)
{
minimize(Tree[i*2].l,x);
minimize(Lazy[i*2].l,x);
minimize(Tree[i*2+1].l,x);
minimize(Lazy[i*2+1].l,x);
}
x=Lazy[i].r;
Lazy[i].r=1;
if(x!=1)
{
maximize(Tree[i*2].r,x);
maximize(Tree[i*2+1].r,x);
maximize(Lazy[i*2].r,x);
maximize(Lazy[i*2+1].r,x);
}
}
void updatel(ll i,ll l,ll r,ll l1,ll r1,ll vl)
{
if(r<l1||r1<l) return;
if(l1<=l&&r<=r1)
{
minimize(Tree[i].l,vl);
minimize(Lazy[i].l,vl);
return;
}
down(i,l,r);
updatel(i*2,l,(l+r)/2,l1,r1,vl);
updatel(i*2+1,(l+r)/2+1,r,l1,r1,vl);
Tree[i].l=min(Tree[i*2].l,Tree[i*2+1].l);
Tree[i].r=max(Tree[i*2].r,Tree[i*2+1].r);
}
void updater(ll i,ll l,ll r,ll l1,ll r1,ll vl)
{
if(r<l1||r1<l) return;
if(l1<=l&&r<=r1)
{
maximize(Tree[i].r,vl);
maximize(Lazy[i].r,vl);
return;
}
down(i,l,r);
updater(i*2,l,(l+r)/2,l1,r1,vl);
updater(i*2+1,(l+r)/2+1,r,l1,r1,vl);
Tree[i].l=min(Tree[i*2].l,Tree[i*2+1].l);
Tree[i].r=max(Tree[i*2].r,Tree[i*2+1].r);
}
void update(ll i,ll l,ll r,ll pos,Range vl)
{
if(r<pos||pos<l) return;
if(l==r)
{
Tree[i]|=vl;
return;
}
down(i,l,r);
update(i*2,l,(l+r)/2,pos,vl);
update(i*2+1,(l+r)/2+1,r,pos,vl);
Tree[i]=Tree[i*2]|Tree[i*2+1];
}
Range query(ll i,ll l,ll r,ll l1,ll r1)
{
if(r<l1||r1<l) return Range(n,1);
if(l1<=l&&r<=r1) return Tree[i];
down(i,l,r);
return query(i*2,l,(l+r)/2,l1,r1)|query(i*2+1,(l+r)/2+1,r,l1,r1);
}
}S[18];
ll n,k,m;
int main()
{
online();
cin>>n>>k>>m;
for(int i=0;i<=17;i++) S[i]=SegmentTree(n);
for(int i=1;i<=m;i++)
{
ll s,t;
cin>>s>>t;
if(s<t)
{
S[0].updater(1,1,n,s,min(s+k-1,t),t);
}
if(s>t)
{
S[0].updatel(1,1,n,max(s-k+1,t),s,t);
}
}
for(int j=1;j<=17;j++)
{
for(int i=1;i<=n;i++)
{
Range x=S[j-1].query(1,1,n,i,i);
x=S[j-1].query(1,1,n,x.l,x.r);
S[j].update(1,1,n,i,x);
}
}
ll q;
cin>>q;
while(q--)
{
ll fr,to;
cin>>fr>>to;
Range x(fr,fr);
ll ans=0,c=(1<<18);
bool flag=0;
for(int i=17;i>=0;i--)
{
c/=2;
Range y=S[i].query(1,1,n,x.l,x.r);
if(y.l<=to&&to<=y.r)
{
flag=1;
continue;
}
x=y;
ans+=c;
}
if(!flag)
{
cout<<"-1\n";
}
else cout<<ans+1<<'\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |