제출 #1249044

#제출 시각아이디문제언어결과실행 시간메모리
1249044_rain_Railway Trip (JOI17_railway_trip)C++20
100 / 100
82 ms17352 KiB
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = (int)1e5; const int MAXLOG = (int)17; int a[N+2] , b[N+2] ,l[N+2]; int lef[N+2][MAXLOG+2] , rig[N+2][MAXLOG+2]; int n,k,q; void process(int l,int r){ if (l>r) swap(l,r); int ans = 0; int t_l , t_r; t_l = t_r = l; for(int j = MAXLOG; j >= 0; --j){ int nxt_r = max(rig[t_l][j] , rig[t_r][j]); int nxt_l = min(lef[t_l][j] , lef[t_r][j]); if (nxt_r < r){ t_r = nxt_r , t_l = nxt_l; ans += (1<<j); } } l = t_r; // cout<<l<<' '<<ans<<'\n'; t_l = t_r = r; for(int j = MAXLOG; j >= 0; --j){ int nxt_r = max(rig[t_l][j] , rig[t_r][j]); int nxt_l = min(lef[t_l][j] , lef[t_r][j]); if (nxt_l > l){ t_r = nxt_r , t_l = nxt_l; ans += (1<<j); } } cout<<ans<<'\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(0) ; cout.tie(0); #define name "main" if (fopen(name".inp","r")){ freopen(name".inp","r",stdin); } cin>>n>>k>>q; for(int i = 1; i <= n; ++i) cin>>l[i]; for(int i = 1; i <= q; ++i) cin>>a[i]>>b[i]; vector<int>st; for(int i = 1; i <= n; ++i) { while (st.size() && l[st.back()] < l[i]) st.pop_back(); if (st.size()) lef[i][0] = st.back(); else lef[i][0] = i; st.push_back(i); } st.clear(); for(int i = n; i >= 1; --i) { while (st.size() && l[st.back()] < l[i]) st.pop_back(); if (st.size()) rig[i][0] = st.back(); else rig[i][0] = i; st.push_back(i); } // for(int i = 1; i <= n; ++i) cout<<i<<' '<<lef[i][0]<<' '<<rig[i][0]<<'\n'; for(int j = 1; j <= MAXLOG; ++j) { for(int i = 1; i <= n; ++i) { int l = min(lef[lef[i][j-1]][j-1],lef[rig[i][j-1]][j-1]); int r = max(rig[lef[i][j-1]][j-1],rig[rig[i][j-1]][j-1]); lef[i][j] = l , rig[i][j] = r; } } for(int i = 1; i <= q; ++i) process(a[i] , b[i]); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:43:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...