Submission #378078

#TimeUsernameProblemLanguageResultExecution timeMemory
378078ScarletSWall (IOI14_wall)C++17
100 / 100
824 ms69740 KiB
#include <bits/stdc++.h> using namespace std; const int INF = 1e5, mn = 2e6+7; int seg[mn<<2][2]; void passDown(int i) { for (int j=i*2+1;j<i*2+3;++j) { seg[j][0]=max(seg[j][0],seg[i][0]); seg[j][1]=max(seg[j][0],seg[j][1]); seg[j][1]=min(seg[j][1],seg[i][1]); seg[j][0]=min(seg[j][0],seg[j][1]); } seg[i][0]=0; seg[i][1]=INF; } void update(int i, int l, int r, int op, int L, int R, int h) { if (R<l||r<L) return; if (L<=l&&r<=R) { if (op==1) { seg[i][0]=max(seg[i][0],h); seg[i][1]=max(seg[i][1],h); } else { seg[i][0]=min(seg[i][0],h); seg[i][1]=min(seg[i][1],h); } return; } passDown(i); update(i*2+1,l,l+(r-l)/2,op,L,R,h); update(i*2+2,l+(r-l)/2+1,r,op,L,R,h); } void calc(int i, int l, int r, int ans[]) { if (l==r) { ans[l]=seg[i][0]; return; } passDown(i); calc(i*2+1,l,l+(r-l)/2,ans); calc(i*2+2,l+(r-l)/2+1,r,ans); } void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) { for (int i=0;i<k;++i) update(0,0,n-1,op[i],l[i],r[i],h[i]); calc(0,0,n-1,ans); } /** int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n,k; cin>>n>>k; int op[k],l[k],r[k],h[k],a[n]; for (int i=0;i<k;++i) cin>>op[i]; for (int i=0;i<k;++i) cin>>l[i]>>r[i]; for (int i=0;i<k;++i) cin>>h[i]; buildWall(n,k,op,l,r,h,a); for (int i=0;i<n;++i) cout<<a[i]<<" "; 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...