Submission #902219

#TimeUsernameProblemLanguageResultExecution timeMemory
902219Sir_Ahmed_ImranWall (IOI14_wall)C++17
8 / 100
3096 ms20092 KiB
///~~~LOTA~~~/// #include "wall.h" #include <bits/stdc++.h> using namespace std; #define nl '\n' #define ff first #define ss second #define ll long long #define append push_back #define pii pair<int,int> #define all(x) (x).begin(),(x).end() #define LIMIT 50000001 #define MAXN 100000 int L[4*MAXN]; int R[4*MAXN]; int ANS[MAXN]; void get(int l=0,int r=MAXN,int v=1,int s=0,int e=MAXN){ l=max(l,L[v]); r=min(r,R[v]); if(e-s==1){ ANS[s]=min(l,r); return; } int lc,rc,mid; lc=2*v; rc=2*v+1; mid=(s+e)/2; get(l,r,lc,s,mid); get(l,r,rc,mid,e); } void update(int l,int r,int x,int i,int v=1,int s=0,int e=MAXN){ if(r<=s || e<=l || s>=e) return; if(l<=s && e<=r){ if(i==1) L[v]=max(L[v],x); else R[v]=min(R[v],x); return; } int lc,rc,mid; lc=2*v; rc=2*v+1; mid=(s+e)/2; update(l,r,x,i,lc,s,mid); update(l,r,x,i,rc,mid,e); } void buildWall(int n,int m,int t[],int l[],int r[],int h[],int ans[]){ for(int i=0;i<4*MAXN;i++) R[i]=MAXN; for(int i=0;i<m;i++){ if(n*m<LIMIT){ for(int j=l[i];j<=r[i];j++){ if(t[i]==1) ANS[j]=max(ANS[j],h[i]); else ANS[j]=min(ANS[j],h[i]); } } else update(l[i],r[i]+1,h[i],t[i]); } if(n*m>=LIMIT) get(); for(int i=0;i<n;i++) ans[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...