제출 #887862

#제출 시각아이디문제언어결과실행 시간메모리
8878621L1YA밀림 점프 (APIO21_jumps)C++17
27 / 100
1883 ms47760 KiB
//1L1YA #include "jumps.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define Pb push_back #define dokme(x) cout << x << endl, exit(0) #define pii pair<int,int> #define F first #define S second #define endl '\n' #define sep ' ' #define all(x) x.begin(),x.end() #define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define lc id<<1 #define rc lc|1 const int N=2e5+5; const int lg=23; int n,a[N],lst[N],nxt[N],sp1[lg][N],sp2[lg][N]; pii seg[N<<2]; void modify(int pos,int val,int id=1,int l=1,int r=n+1){ if(r-l==1){ seg[id]={val,pos}; return; } int mid=l+r>>1; if(pos<mid) modify(pos,val,lc,l,mid); else modify(pos,val,rc,mid,r); if(seg[lc].F>seg[rc].F) seg[id]=seg[lc]; else seg[id]=seg[rc]; } pii get(int ql,int qr,int id=1,int l=1,int r=n+1){ if(qr<=l || ql>=r) return {0,0}; if(ql<=l && r<=qr) return seg[id]; int mid=l+r>>1; pii p1=get(ql,qr,lc,l,mid),p2=get(ql,qr,rc,mid,r); if(p1.F>p2.F) return p1; else return p2; } void init(int m, std::vector<int> h) { n=m; for(int i=1;i<=n;i++) a[i]=h[i-1]; a[0]=a[n+1]=n+1; vector<int> st; st.Pb(0); for(int i=1;i<=n;i++){ while(a[st.back()]<a[i]) st.pop_back(); lst[i]=st.back(); st.Pb(i); } st.clear(); st.Pb(n+1); for(int i=n;i;i--){ while(a[st.back()]<a[i]) st.pop_back(); nxt[i]=st.back(); st.Pb(i); } for(int i=1;i<=n;i++){ sp1[0][a[i]]=min(a[lst[i]],a[nxt[i]]); sp2[0][a[i]]=max(a[lst[i]],a[nxt[i]]); } sp1[0][n+1]=sp2[0][n+1]=n+1; for(int i=n+1;i;i--) for(int j=1;j<lg;j++){ sp1[j][i]=sp1[j-1][sp1[j-1][i]]; sp2[j][i]=sp2[j-1][sp2[j-1][i]]; } for(int i=1;i<=n;i++) modify(i,a[i]); } int dist(int s,int e){ int ans=0; for(int i=lg-1;~i;i--) if(sp2[i][s]<e) s=sp2[i][s],ans+=1<<i; if(sp2[0][s]==e) return ans+1; for(int i=lg-1;~i;i--) if(sp1[i][s]<e) s=sp1[i][s],ans+=1<<i; return ans+1; } int minimum_jumps(int l1, int r1, int l2, int r2){ l1++;r1++;l2++;r2++; int mx=get(l2,r2+1).F; if(get(r1,l2).F>mx) return -1; int l=0,r=r1; while(r-l>1){ int mid=l+r>>1; if(get(mid,r1+1).F<mx) r=mid; else l=mid; } int x=get(l1,r1+1).S,p=r; mx=get(l1,l2).F; l=l2-1,r=r2; while(r-l>1){ int mid=l+r>>1; if(get(l2,mid+1).F<mx) l=mid; else r=mid; } int ans=dist(a[x],a[r]); if(get(p,l2).F>mx){ l=p,r=l2; while(r-l>1){ int mid=l+r>>1; if(get(mid,l2).F<mx) r=mid; else l=mid; } mx=a[l]; l=l2-1,r=r2; while(r-l>1){ int mid=l+r>>1; if(get(l2,mid+1).F<mx) l=mid; else r=mid; } ans=min(ans,dist(a[x],a[r])); } return ans; }

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

jumps.cpp: In function 'void modify(int, int, int, int, int)':
jumps.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         int mid=l+r>>1;
      |                 ~^~
jumps.cpp: In function 'std::pair<int, int> get(int, int, int, int, int)':
jumps.cpp:39:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int mid=l+r>>1;
      |                 ~^~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:100:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |             int mid=l+r>>1;
      |                     ~^~
jumps.cpp:108:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |             int mid=l+r>>1;
      |                     ~^~
jumps.cpp:116:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |                 int mid=l+r>>1;
      |                         ~^~
jumps.cpp:123:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |                 int mid=l+r>>1;
      |                         ~^~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...