제출 #536799

#제출 시각아이디문제언어결과실행 시간메모리
536799kymRailway Trip 2 (JOI22_ho_t4)C++14
0 / 100
210 ms59800 KiB
#include <bits/stdc++.h> using namespace std; #define int ll #define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i) #define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i) #define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL #define db(x) cerr << #x << "=" << x << "\n" #define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n" #define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n" #define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n" #define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{" << ite.f << ',' << ite.s << "} "; cerr << "\n" #define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n" #define reach cerr << "LINE: " << __LINE__ << "\n"; #else #define db(x) #define db2(x,y) #define db3(a,b,c) #define dbv(v) #define dbvp(v) #define dba(a,ss,ee) #define reach #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define ll long long #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define f first #define s second #define g0(x) get<0>(x) #define g1(x) get<1>(x) #define g2(x) get<2>(x) #define g3(x) get<3>(x) typedef pair <ll, ll> pi; typedef tuple<ll,ll,ll> ti3; typedef tuple<ll,ll,ll,ll> ti4; ll rand(ll a, ll b) { return a + rng() % (b-a+1); } const int MOD = 1e9 + 7; const int inf = (int)1e9 + 500; const long long oo = (ll)1e18 + 500; template <typename T> void chmax(T& a, const T b) { a=max(a,b); } template <typename T> void chmin(T& a, const T b) { a=min(a,b); } const int MAXN = 100005; int n,k,m; pi A[MAXN]; int Q; struct node { int s,e,m,val,lazymx; node *l, *r; node (int _s, int _e) { s=_s,e=_e; m=(s+e)/2; lazymx=oo; if(s!=e){ l=new node(s,m); r=new node(m+1,e); } } void set(int x, int nval) { if(s==e){ val=nval; return; } else { if(x>m)r->set(x,nval); else l->set(x,nval); val=max(l->val,r->val); } } void value() { if(s==e) { if(lazymx==oo)return; val=max(val,lazymx); lazymx=oo; return; } if(lazymx != oo){ chmax(l->val,lazymx); chmax(r->val,lazymx); lazymx=oo; return; } } void range_set(int x, int y, int nval) { value(); if(s==x&&e==y) { lazymx=nval; return; } if(x>m)r->range_set(x,y,nval); else if(y<=m)l->range_set(x,y,nval); else l->range_set(x,m,nval), r->range_set(m+1,y,nval); l->value(); r->value(); val=max(l->val,r->val); } int query(int x) { value(); if(s==e) return val; if(x>m)return r->query(x); else return l->query(x); } } *normal, *back; int fronttk[MAXN][21]; int backttk[MAXN][21]; int32_t main() { IAMSPEED cin >> n >> k >> m; FOR(i,1,m) cin>> A[i].f >> A[i].s; normal = new node(1,n); back = new node(1,n); FOR(i,1,n) { normal->set(i,i); back->set(i,-i); } FOR(i,1,m) { if(A[i].f < A[i].s) { normal->range_set(A[i].f, min(A[i].f + k - 1, A[i].s-1), A[i].s); } else { back->range_set(max(A[i].f-k+1,A[i].s+1), A[i].f, -A[i].s); } } memset(fronttk,-1,sizeof fronttk); memset(backttk,-1,sizeof backttk); FOR(i,1,n) { fronttk[i][0] = normal->query(i); backttk[i][0] = -back->query(i); } DEC(i,n,1) { FOR(j,1,20) { if(fronttk[i][j-1]==-1)break; fronttk[i][j] = fronttk[fronttk[i][j-1]][j-1]; } } FOR(i,1,n) { FOR(j,1,20) { if(backttk[i][j-1]==-1)break; backttk[i][j] = backttk[backttk[i][j-1]][j-1]; } } int Q; cin >> Q; while(Q--) { int x, y; cin >> x >> y; if(x<y) { int ans =0 ; DEC(i,20,0) { if(fronttk[x][i] != -1 && fronttk[x][i] < y){ ans += 1ll<<i; x=fronttk[x][i]; } } ++ans; if(ans==2097152||fronttk[x][0]==-1||fronttk[x][0]<y)ans=-1; cout << ans << '\n'; } else { int ans =0 ; DEC(i,20,0) { if(backttk[x][i] != -1 && backttk[x][i] > y){ ans += 1ll<<i; x=backttk[x][i]; } } ++ans; if(ans==2097152||backttk[x][0]==-1||backttk[x][0]>y)ans=-1; cout << ans << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...