Submission #1099974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099974		vjudge1	Wall (IOI14_wall)	C++17	61 / 100	776 ms	262148 KiB

wall

#include <iostream>
#include <map>
#include <unordered_map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include "wall.h"
using namespace std;
#define ll long long
#define PLL pair<ll, ll>
#define PB push_back
#define F first
#define S second
#define MP make_pair

void build(ll v, ll l, ll r, vector<PLL> &t, vector<PLL> &actu){
    actu[v].F = -1;
    actu[v].S = -1;
    if(l==r){
        t[v] = MP(0ll,0ll);
        return;
    }
    ll m = (l+r)/2;
    build(2*v,l,m,t,actu);
    build(2*v+1,m+1,r,t,actu);
    t[v].F = min(t[2*v].F,t[2*v+1].F);
    t[v].S = max(t[2*v].S,t[2*v+1].S);
}

void propagate(ll v, ll l, ll r, vector<PLL>&t, vector<PLL>&actu){
  //cout<<"propagating: "<<v<<" "<<l<<" "<<r<<endl;
  //cout<<t[v].F<<" "<<t[v].S<<endl;

  //cout<<actu[v].F<<" "<<actu[v].S<<endl;
    if(actu[v].F!=-1){
        //if(t[v].S>actu[v].F){
            t[v].S = min(actu[v].F,t[v].S);
            t[v].F = min(t[v].F,actu[v].F);
            if(l!=r){
                actu[2*v].F = min(actu[v].F,actu[2*v].F);
                if(actu[2*v].F==-1){
                    actu[2*v].F = actu[v].F;
                }
                if(actu[2*v].S>actu[v].F){
                    actu[2*v].S = actu[v].F;
                    actu[2*v].F = actu[v].F;
                }
                actu[2*v+1].F = min(actu[v].F,actu[2*v+1].F);
                if(actu[2*v+1].F==-1){
                    actu[2*v+1].F = actu[v].F;
                }
                if(actu[2*v+1].S>actu[v].F){
                    actu[2*v+1].S = actu[v].F;
                    actu[2*v+1].F = actu[v].F;
                }
            }
        //}
        actu[v].F = -1;
    }
    if(actu[v].S!=-1){
        //if(t[v].F<actu[v].S){
            t[v].F = max(actu[v].S,t[v].F);
            t[v].S = max(t[v].S,actu[v].S);
            if(l!=r){
                actu[2*v].S = max(actu[v].S,actu[2*v].S);
                if(actu[2*v].F<actu[v].S and actu[2*v].F!=-1){
                    actu[2*v].F = actu[v].S;
                    actu[2*v].S = actu[v].S;
                }
                actu[2*v+1].S = max(actu[v].S,actu[2*v+1].S);
                if(actu[2*v+1].F<actu[v].S and actu[2*v+1].F!=-1){
                    actu[2*v+1].F = actu[v].S;
                    actu[2*v+1].S = actu[v].S;
                }
            }
        //}
        actu[v].S = -1;
    }
    //cout<<t[v].F<<" "<<t[v].S<<endl;
}

void adding(ll v, ll l, ll r, ll lx, ll rx, ll h, vector<PLL>&t, vector<PLL>&actu){ 
    if(actu[v].F!=-1 or actu[v].S!=-1){
        propagate(v,l,r,t,actu);
    } 
    if(lx<=l and r<=rx){
        if(actu[v].F<h and actu[v].F !=-1){
            actu[v].S = h;
            actu[v].F = h;
        }
        else{
            actu[v].S = max(actu[v].S,h);
        }
        propagate(v,l,r,t,actu);
        return;
    }
    if(l>rx or r<lx){
        return;
    }
    ll m = (l+r)/2;
    adding(2*v,l,m,lx,rx,h,t,actu);
    adding(2*v+1,m+1,r,lx,rx,h,t,actu);
    t[v].F = min(t[2*v].F,t[2*v+1].F);
    t[v].S = max(t[2*v].S,t[2*v+1].S);
}

void removing (ll v, ll l, ll r, ll lx, ll rx, ll h, vector<PLL>&t, vector<PLL>&actu){  
    if(actu[v].F!=-1 or actu[v].S!=-1){
        propagate(v,l,r,t,actu);
    }
    if(lx<=l and r<=rx){
        //actu[v].F = h;
        if(actu[v].S>h){
            actu[v].S = h;
            actu[v].F = h;
        }
        else if(actu[v].F!=-1){
            actu[v].F = min(actu[v].F,h);
        }
        else{
            actu[v].F = h;
        }
        propagate(v,l,r,t,actu);
        return;
    }
    if(l>rx or r<lx){
        return;
    }
    ll m = (l+r)/2;
    removing(2*v,l,m,lx,rx,h,t,actu);
    removing(2*v+1,m+1,r,lx,rx,h,t,actu);
    t[v].F = min(t[2*v].F,t[2*v+1].F);
    t[v].S = max(t[2*v].S,t[2*v+1].S);
}

void recover(ll v, ll l, ll r, vector<PLL> &t,vector<PLL> &actu, vector<int> &ans){
    //cout<<v<<" "<<l<<" "<<r<<endl;
    if(actu[v].F!=-1 or actu[v].S!=-1){
        propagate(v,l,r,t,actu); 
    }
    if(l==r){
        //cout<<t[v].F<<endl;
        ans[l] = t[v].F;
        return;
    }
    ll m = (l+r)/2;
    recover(2*v,l,m,t,actu,ans);
    recover(2*v+1,m+1,r,t,actu,ans);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    vector<PLL> t(4*n), actu(4*n);
    build(1,0,n-1,t,actu);
    for(ll i=0; i<k; i++){
        //cout<<"### "<<i<<" ###"<<endl;
        if(op[i]==1){
            adding(1,0,n-1,left[i],right[i],height[i],t,actu);
        }
        else{
            removing(1,0,n-1,left[i],right[i],height[i],t,actu);
        }
    }
    vector<int> ans(n);
    recover(1,0,n-1,t,actu,ans);
    for(int i=0; i<n; i++){
        finalHeight[i] = (int)ans[i];
    }
    return;
}

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