This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> seg,arr,lazy,seg1,lazy1;
class SGT{
public:
SGT(ll n){
seg.resize(4*n + 3,0);
lazy.resize(4*n + 3,0);
}
void update(ll l,ll r,ll ind,ll left,ll right,ll val){
if(lazy[ind]!=0){
ll am = lazy[ind];
seg[ind]=max(seg[ind],am);
if(l!=r){
lazy[2*ind+1] = max(lazy[2*ind+1],lazy[ind]);
lazy[2*ind+2] = max(lazy[2*ind+2],lazy[ind]);
}
lazy[ind]=0;
}
if(r<left||l>right) return;
if(r<=right&&l>=left){
ll am = val;
seg[ind]=max(seg[ind],am);
if(l!=r){
lazy[2*ind+1] = max(lazy[2*ind+1],lazy[ind]);
lazy[2*ind+2] = max(lazy[2*ind+2],lazy[ind]);
}
return;
}
ll mid = (l+r)/2;
update(l,mid,2*ind+1,left,right,val);
update(mid+1,r,2*ind+2,left,right,val);
//seg[ind]=max({seg[ind],seg[2*ind+1],seg[2*ind+2]});
}
};
class SGT2{
public:
SGT2(ll n){
seg1.clear();
lazy1.clear();
seg1.resize(4*n + 3,1e9);
lazy1.resize(4*n + 3,1e9);
}
void update(ll l,ll r,ll ind,ll left,ll right,ll val){
if(lazy1[ind]!=1e9){
ll am = lazy1[ind];
seg1[ind]=min(seg1[ind],am);
if(l!=r){
lazy1[2*ind+1] = min(lazy1[2*ind+1],lazy1[ind]);
lazy1[2*ind+2] = min(lazy1[2*ind+2],lazy1[ind]);
}
lazy1[ind]=1e9;
}
if(r<left||l>right) return;
if(r<=right&&l>=left){
ll am = val;
seg1[ind]=min(seg1[ind],am);
if(l!=r){
lazy1[2*ind+1] = min(lazy1[2*ind+1],lazy1[ind]);
lazy1[2*ind+2] = min(lazy1[2*ind+2],lazy1[ind]);
}
return;
}
ll mid = (l+r)/2;
update(l,mid,2*ind+1,left,right,val);
update(mid+1,r,2*ind+2,left,right,val);
//seg[ind]=max({seg[ind],seg[2*ind+1],seg[2*ind+2]});
}
};
void dfs(ll ind,ll l,ll r,ll maxi,int finalHeight[]){
if(l==r){
maxi = max({maxi,lazy[ind],seg[ind]});
finalHeight[l]=max((ll) finalHeight[l],maxi);
return;
}
ll mid = (l+r)/2;
maxi = max({maxi,lazy[ind],seg[ind]});
dfs(2*ind+1,l,mid,maxi,finalHeight);
dfs(2*ind+2,mid+1,r,maxi,finalHeight);
}
void dfs2(ll ind,ll l,ll r,ll maxi,int finalHeight[]){
if(l==r){
maxi = min({maxi,lazy1[ind],seg1[ind]});
finalHeight[l]=min((ll) finalHeight[l],maxi);
return;
}
ll mid = (l+r)/2;
maxi = min({maxi,lazy1[ind],seg1[ind]});
dfs2(2*ind+1,l,mid,maxi,finalHeight);
dfs2(2*ind+2,mid+1,r,maxi,finalHeight);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<n;i++){
finalHeight[i]=0;
}
if(n<=10000&&k<=5000){
for(int i=0;i<k;i++){
int o = op[i];
for(int j=left[i];j<=right[i];j++){
if(finalHeight[j]<height[i] && o==1) finalHeight[j] = height[i];
if(finalHeight[j]>height[i] && o==2) finalHeight[j] = height[i];
}
}
return;
}
bool ok=1;
SGT sg(n);
SGT2 sg2(n);
for(int i=0;i<k;i++){
int o = op[i];
if(o==1){
sg.update(0,n-1,0,left[i],right[i],height[i]);
continue;
}
if(o==2 && ok==1){
ok=0;
}
sg2.update(0,n-1,0,left[i],right[i],height[i]);
}
dfs(0,0,n-1,0,finalHeight);
dfs2(0,0,n-1,1e9,finalHeight);
return;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |