Submission #974200

#TimeUsernameProblemLanguageResultExecution timeMemory
974200berrRailway Trip 2 (JOI22_ho_t4)C++17
100 / 100
601 ms64568 KiB
#include <bits/stdc++.h> using namespace std; const int N = 505; struct segtree{ int n, tl, tr, type; vector<int> st, a; int merge(int x, int y){ if(type==0) return min(x, y); return max(x, y); } segtree(vector<int> x, int t){ n=x.size(); type = t; a=x; st.resize(2*n); for(int i=0; i<n; i++) st[i+n]=x[i]; for(int i=n-1; i>=0; i--) st[i]=merge(st[i*2], st[i*2+1]); } int operator()(int l, int r){ int base=a[l]; for(l+=n, r+=n+1; l!=r; l/=2, r/=2){ if(l&1) base=merge(base, st[l++]); if(r&1) base=merge(base, st[--r]); } return base; } }; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, k, m; cin >> n >> k >> m; vector<int> l(n), r(n); priority_queue<array<int, 2>> q; iota(l.begin(), l.end(), 0); iota(r.begin(), r.end(), 0); vector<array<int, 2>> e(m); for(auto &[i, l]: e) cin >> i >> l, i--, l--; sort(e.begin(), e.end()); int pos=0; for(int i=0; i<n; i++){ while(pos<m && e[pos][0]==i) q.push({e[pos][1], e[pos][0]}), pos++; while(q.size()&&q.top()[1] < i-k+1) q.pop(); if(q.size()) if(q.size()) r[i]=max(r[i], q.top()[0]); } while(q.size()) q.pop(); reverse(e.begin(), e.end()); pos = 0; for(int i=n-1; i>=0; i--){ while(pos<m && e[pos][0]==i) q.push({-e[pos][1], e[pos][0]}), pos++; while(q.size()&&q.top()[1] > i+k-1) q.pop(); if(q.size()) l[i]=min(l[i], -q.top()[0]); } vector<vector<int>> left, right; left.push_back(l); right.push_back(r); vector<segtree> left_st, right_st; for(int i=1; i<=n; i*=2){ segtree l(left.back(), 0), r(right.back(), 1); vector<int> l_new(n), r_new(n); for(int i=0; i<n; i++){ l_new[i]=l(left.back()[i], right.back()[i]); r_new[i]=r(left.back()[i], right.back()[i]); } left_st.push_back(l); right_st.push_back(r); left.push_back(l_new); right.push_back(r_new); } int qe; cin >> qe; while(qe--){ int x, y; cin >> x >> y; x--; y--; int s=0; int le=-1, re=-1, pos=-1, ans=0; for(int i=left.size()-1; i>=0; i--){ int tl=left[i][x], tr=right[i][x]; if(tl<= y&&y<=tr) continue; else{ le=tl; re=tr; pos=i; ans+=(1<<i); break; } } if(le==-1 && re==-1) cout<<1<<"\n"; else{ for(int i=pos-1; i>=0; i--){ int vl=left_st[i](le, re), vr=right_st[i](le, re); if(vl <= y && y<=vr){ continue; } else{ le=min(vl, le); re=max(re, vr); ans+=(1<<i); } } ans++; int tl=(left_st[0](le, re)); int tr=right_st[0](le, re); if(tl<=y&&y<=tr) cout<<ans<<"\n"; else cout<<-1<<"\n"; } } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:103:13: warning: unused variable 's' [-Wunused-variable]
  103 |         int s=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...