#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb puodsh_back
#define a first
#define b second
#include "wall.h"
int tree[8000000];
int lazy[8000000][2];
int ans[2000000];
int k;
void update(int no,int l,int r,int aa,int bb,int val,int tt){
if(tree[no]<lazy[no][0]){
tree[no]=lazy[no][0];
}
else if(tree[no]>lazy[no][1]){
tree[no]=lazy[no][1];
}
if(l==r){
lazy[no][0]=0;
lazy[no][1]=k-1;
}
if(l<r){
if(lazy[no][0]>lazy[no*2+1][1]){
lazy[no*2+1][0]=lazy[no][0];
lazy[no*2+1][1]=lazy[no][0];
}
else if(lazy[no][1]<lazy[no*2+1][0]){
lazy[no*2+1][0]=lazy[no][1];
lazy[no*2+1][1]=lazy[no][1];
}
else{
lazy[no*2+1][0]=max(lazy[no][0],lazy[no*2+1][0]);
lazy[no*2+1][1]=min(lazy[no][1],lazy[no*2+1][1]);
}
if(lazy[no][0]>lazy[no*2+2][1]){
lazy[no*2+2][0]=lazy[no][0];
lazy[no*2+2][1]=lazy[no][0];
}
else if(lazy[no][1]<lazy[no*2+2][0]){
lazy[no*2+2][0]=lazy[no][1];
lazy[no*2+2][1]=lazy[no][1];
}
else{
lazy[no*2+2][0]=max(lazy[no][0],lazy[no*2+2][0]);
lazy[no*2+2][1]=min(lazy[no][1],lazy[no*2+2][1]);
}
lazy[no][0]=0;
lazy[no][1]=k-1;
}
if(r<aa or l>bb or l>r){
return ;
}
if(aa<=l and r<=bb){
if(tt==0){
tree[no]=min(tree[no],val);
}
else{
tree[no]=max(tree[no],val);
}
// cout<<l<<","<<r<<","<<val<<","<<tree[no]<<"<"<<no<<endl;
if(l<r){
if(tt==0){
lazy[no*2+1][0]=min(lazy[no*2+1][0],val);
lazy[no*2+1][1]=min(lazy[no*2+1][1],val);
}
else{
lazy[no*2+1][0]=max(lazy[no*2+1][0],val);
lazy[no*2+1][1]=max(lazy[no*2+1][1],val);
}
if(tt==0){
lazy[no*2+2][0]=min(lazy[no*2+2][0],val);
lazy[no*2+2][1]=min(lazy[no*2+2][1],val);
}
else{
lazy[no*2+2][0]=max(lazy[no*2+2][0],val);
lazy[no*2+2][1]=max(lazy[no*2+2][1],val);
}
}
}
else{
int mid=(l+r)/2;
update(no*2+1,l,mid,aa,bb,val,tt);
update(no*2+2,mid+1,r,aa,bb,val,tt);
}
}
int fin(int no,int l,int r){
if(tree[no]<lazy[no][0]){
tree[no]=lazy[no][0];
}
else if(tree[no]>lazy[no][1]){
tree[no]=lazy[no][1];
}
if(l==r){
lazy[no][0]=0;
lazy[no][1]=k-1;
}
if(l<r){
if(lazy[no][0]>lazy[no*2+1][1]){
lazy[no*2+1][0]=lazy[no][0];
lazy[no*2+1][1]=lazy[no][0];
}
else if(lazy[no][1]<lazy[no*2+1][0]){
lazy[no*2+1][0]=lazy[no][1];
lazy[no*2+1][1]=lazy[no][1];
}
else{
lazy[no*2+1][0]=max(lazy[no][0],lazy[no*2+1][0]);
lazy[no*2+1][1]=min(lazy[no][1],lazy[no*2+1][1]);
}
if(lazy[no][0]>lazy[no*2+2][1]){
lazy[no*2+2][0]=lazy[no][0];
lazy[no*2+2][1]=lazy[no][0];
}
else if(lazy[no][1]<lazy[no*2+2][0]){
lazy[no*2+2][0]=lazy[no][1];
lazy[no*2+2][1]=lazy[no][1];
}
else{
lazy[no*2+2][0]=max(lazy[no][0],lazy[no*2+2][0]);
lazy[no*2+2][1]=min(lazy[no][1],lazy[no*2+2][1]);
}
lazy[no][0]=0;
lazy[no][1]=k-1;
}
if(l==r){
ans[l]=tree[no];
}
if(l<r){
int mid=(l+r)/2;
fin(no*2+1,l,mid);
fin(no*2+2,mid+1,r);
}
}
void buildWall(int n, int kk, int op[], int left[], int right[],int height[], int finalHeight[]){
for(int i=0;i<4*n;i++){
lazy[i][0]=0;
lazy[i][1]=k-1;
tree[i]=0;
}
k=kk;
for(int i=0;i<kk;i++){
if(op[i]==1){
update(0,0,n-1,left[i],right[i],height[i],1);
}
else{
update(0,0,n-1,left[i],right[i],height[i],0);
}
}
// cout<<tree[16]<<endl;
fin(0,0,n-1);
for(int i=0;i<n;i++){
finalHeight[i]=ans[i];
// cout<<ans[i]<<" ";
}
// return finalHeight;
// cout<<endl;
}
/*int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int op[6];
int left[6];int right[6];int height[6];
op[0]=1;
left[0]=1;
right[0]=8;
height[0]=4;
op[1]=2;
left[1]=4;
right[1]=9;
height[1]=1;
op[2]=2;
left[2]=3;
right[2]=6;
height[2]=5;
op[3]=1;
left[3]=0;
right[3]=5;
height[3]=3;
op[4]=1;
left[4]=2;
right[4]=2;
height[4]=5;
op[5]=2;
left[5]=6;
right[5]=7;
height[5]=0;
int ar[10];
buildWall(10,6,op,left,right,height,ar);
for(int i=0;i<10;i++){
cout<<ar[i]<<" ";
}
cout<<endl;
return 0;
}*/
Compilation message
wall.cpp: In function 'int fin(int, int, int)':
wall.cpp:139:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
