Submission #122609

#	Time	Username	Problem	Language	Result	Execution time	Memory
122609		brcode	Wall (IOI14_wall)	C++14	0 / 100	228 ms	9976 KiB

wall

#include <iostream>
#include "wall.h"
using namespace std;
struct node{
    int mn,mx;
};
const int MAXN = 4e6+5;
pair<int,int> lazy[4*MAXN];
int ans[MAXN];
int seg[4*MAXN];
void push(int curr,int l,int r){
    if(lazy[curr].first == -1e9 && lazy[curr].second == -1e9){
        return;
    }
    seg[curr] = max(seg[curr],lazy[curr].first);
    seg[curr] = min(seg[curr],lazy[curr].second);
    if(l!=r){
        auto a = lazy[2*curr];
        auto b = lazy[curr];
        if(b.second<=a.first){
            a = make_pair(b.second,b.second);
        }else if(b.first>=a.second){
            a = make_pair(b.first,b.first);
        }else{
            a.first = max(a.first,b.first);
            a.second = max(a.second,b.second);
        }
        lazy[2*curr] = a;
        a= lazy[2*curr+1];
        b = lazy[curr];
        if(b.second<=a.first){
            a = make_pair(b.second,b.second);
        }else if(b.first>=a.second){
            a = make_pair(b.first,b.first);
        }else{
            a.first = max(a.first,b.first);
            a.second = max(a.second,b.second);
        }
        lazy[2*curr+1] = a;
    }
    lazy[curr] = make_pair(-1e9,1e9);
}
void update(int curr,int l,int r,int tl,int tr,pair<int,int> p1){
    push(curr,l,r);
    if(l>tr||r<tl){
        return;
    }
    if(l>=tl && r<=tr){
        lazy[curr] = p1;
        push(curr,l,r);
        return;
    }
    int mid = (l+r)/2;
    update(2*curr,l,mid,tl,tr,p1);
    update(2*curr+1,mid+1,r,tl,tr,p1);
}
void solve(int curr,int l,int r){
    push(curr,l,r);
    if(l==r){
        ans[l-1] = seg[curr];
        return;
    }
    int mid = (l+r)/2;
    solve(2*curr,l,mid);
    solve(2*curr+1,mid+1,r);
    
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
    
   
    
    for(int i=0;i<k;i++){
        if(op[i] == 1){
            update(1,1,n,left[i]+1,right[i]+1,make_pair(height[i],1e9));
        }else{
            update(1,1,n,left[i]+1,right[i]+1,make_pair(-1e9,height[i]));
        }
        
    }
    solve(1,1,n);
    for(int i=0;i<n;i++){
        finalHeight[i] = ans[i];
        //cout<<i<<" "<<ans[i]<<endl;
    }
}
/*int main(){
    int n,k;
    cin>>n>>k;
    int left[k+1];
    int right[k+1];
    int height[k+1];
    int type[k+1];
    int finalHeight[k+1];
    for(int i=0;i<k;i++){
        cin>>type[i]>>left[i]>>right[i]>>height[i];
    }
    buildWall(n,k,type,left,right,height,finalHeight);
}*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39