제출 #530313

#제출 시각아이디문제언어결과실행 시간메모리
530313yungyaoRailway Trip 2 (JOI22_ho_t4)C++17
27 / 100
2051 ms3628 KiB
using namespace std; #include <iostream> #include <algorithm> #include <utility> #include <vector> #include <stack> #include <queue> #include <set> #include <map> typedef long long LL; typedef pair<int,int> pii; #define pb push_back #define mkp make_pair #define F first #define S second #define iter(x) x.begin(),x.end() #define REP(n) for (int __=n;__--;) #define REP0(i,n) for (int i=0;i<n;++i) #define REP1(i,n) for (int i=1;i<=n;++i) const int maxn = 1e5+10, mod = 0; const LL inf = 0; int mx[maxn], mn[maxn]; struct segmenttree{ int val[maxn*4], type; int pull(int l, int r){ return type == 1 ? max(l, r) : min(l, r); } void maketree(int cur, int LB, int RB){ if (LB == RB){ if (type == 1) val[cur] = mx[LB]; else val[cur] = mn[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]); } } void init(int n, int _type){ type = _type; maketree(1, 1 ,n); } int 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[2]; void solve(){ int n, k, m, q; cin >> n >> k >> m; REP1(i, n) mn[i] = mx[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.push_back(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.push_back(mkp(mn[i], i)); if (dq.front().S - k >= i) dq.pop_front(); mn[i] = dq.front().F; } seg[0].init(n, 1); seg[1].init(n, 2); cin >> q; REP(q){ int s, t; cin >> s >> t; pii r = mkp(s, s); int cnt = 0; while (t < r.F or t > r.S){ ++cnt; pii nr = mkp(seg[1].query(r.F, r.S, 1, 1, n), seg[0].query(r.F, r.S, 1, 1, n)); if (r == nr){ cnt = -1; break; } r = nr; } cout << cnt << '\n'; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); solve(); return 0; }
#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...