Submission #782682

#TimeUsernameProblemLanguageResultExecution timeMemory
782682TrumlingWall (IOI14_wall)C++14
100 / 100
594 ms193340 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define F first #define S second #define enter cout<<'\n'; long long INF=99999999999999; #define MOD 1000000007 #define all(x) x.begin(),x.end() struct node { ll m=INF; ll M=0; }; ll ans[3000000]; node seg[9000000]; void lazy(int idx) { seg[idx*2].m=max(seg[idx].M,seg[idx*2].m); seg[idx*2].M=max(seg[idx].M,seg[idx*2].M); seg[idx*2].m=min(seg[idx].m,seg[idx*2].m); seg[idx*2].M=min(seg[idx].m,seg[idx*2].M); seg[idx*2+1].m=max(seg[idx].M,seg[idx*2+1].m); seg[idx*2+1].M=max(seg[idx].M,seg[idx*2+1].M); seg[idx*2+1].m=min(seg[idx].m,seg[idx*2+1].m); seg[idx*2+1].M=min(seg[idx].m,seg[idx*2+1].M); seg[idx]={INF,0}; return ; } void up(int l,int r,int idx,int op,ll u,int L,int R) { if(l>R || r<L) return ; if(L<=l && r<=R) { if(op==1) { seg[idx].m=max(seg[idx].m,u); seg[idx].M=max(seg[idx].M,u); } else { seg[idx].m=min(seg[idx].m,u); seg[idx].M=min(seg[idx].M,u); } return ; } lazy(idx); up(l,(l+r)/2,idx*2,op,u,L,R); up((l+r)/2+1,r,idx*2+1,op,u,L,R); } void fin(int l,int r,int idx) { if(l==r) { ans[l]=seg[idx].M; return ; } lazy(idx); fin(l,(l+r)/2,idx*2); fin((l+r)/2+1,r,idx*2+1); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { for(int i=0;i<k;i++) up(0,n-1,1,op[i],height[i],left[i],right[i]); fin(0,n-1,1); for(int i=0;i<n;i++) finalHeight[i]=ans[i]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...