Submission #276933

#	Time	Username	Problem	Language	Result	Execution time	Memory
276933		Dremix10	Wall (IOI14_wall)	C++17	100 / 100	913 ms	151800 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x)
    #define p2(x,y)
    #define pp(x)
    #define pv(x)
    #define ppv(x)
#endif
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 1e18;
const int MOD = 1e9+7;
const int N = 2e5+1;

template<typename T>
struct SEGTREE{
    struct node{
        T val; // for adding more stuff
        T mini,maxi,rep;

        node() : val(0), mini(-1), maxi(-1), rep(-1) {}
        node(T _val) : val(_val), mini(-1), maxi(-1), rep(-1) {}
    };
    vector<node> seg;
    int N;

    void init(int n){
        N = n;
        seg.assign(4*n,node());
    }

    node merge(node x, node y){
        node res;
        return res;
    }

    void look(node x){
        cout<<x.val<<" "<<x.mini<<" "<<x.maxi<<" "<<x.rep<<endl;
    }

    void add(node &x, int val){
        /// if both then max<min
        if(x.rep!=-1){
            x.rep = max(x.rep,val);
            x.val = x.rep;
            return;
        }
        x.maxi = max(x.maxi,val);
        if(x.mini !=-1 && x.mini <= x.maxi){
            x.rep = x.maxi;
            x.mini = -1;
            x.maxi = -1;
            x.val = x.rep;
        }
        else{
            x.val = max(x.val,x.maxi);
            if(x.mini!=-1)
                x.val = min(x.val,x.mini);
        }
    }

    void rem(node &x, int val){
        /// if both then max < min
        if(x.rep!=-1){
            x.rep = min(x.rep,val);
            x.val = x.rep;
            return;
        }
        if(x.mini == -1)x.mini = val;
        else x.mini = min(x.mini,val);
        if(x.mini <= x.maxi){
            x.rep = x.mini;
            x.mini = -1;
            x.maxi = -1;
            x.val = x.rep;
        }
        else{
            x.val = max(x.val,x.maxi);
            x.val = min(x.val,x.mini);
        }
    }

    void push(node &par, node &x, node &y, int r1, int r2){
        if(par.rep!=-1){
            x.val = par.rep;
            x.rep = par.rep;
            x.mini = -1;
            x.maxi = -1;
            y.val = par.rep;
            y.rep = par.rep;
            y.mini = -1;
            y.maxi = -1;
            par.rep = -1;
            return;
        }
        if(par.maxi!=-1){
            add(x,par.maxi);
            add(y,par.maxi);
        }
        if(par.mini!=-1){
            rem(x,par.mini);
            rem(y,par.mini);
        }
        par.maxi = -1;
        par.mini = -1;
    }

    void build(int s, int e, int idx, T arr[]){
        if(s == e){
            seg[idx] = node(arr[s]);
            return;
        }
        int mid = (s+e)/2;
        build(s,mid,idx*2,arr);
        build(mid+1,e,idx*2+1,arr);
        seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
    }

    // supports 1-indexing
    void build(T arr[]){
        build(1,N,1,arr);
    }

    /// add
    void update1(int s, int e, int idx, int qs, int qe, T val){
        //cout<<s<<" "<<e<<endl;
        //look(seg[idx]);
        if(qs<=s && e<=qe){
            add(seg[idx],val);
            //look(seg[idx]);
            return;
        }
        if(s>qe || e<qs)
            return;
        int mid = (s+e)/2;
        push(seg[idx],seg[idx*2],seg[idx*2+1],mid-s+1,e-mid);
        update1(s,mid,idx*2,qs,qe,val);
        update1(mid+1,e,idx*2+1,qs,qe,val);
        seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
    }

    // add to all i (l<=i && i<=r) += val
    void update1(int l, int r, T val){
        update1(1,N,1,l,r,val);
    }

    /// rem
    void update2(int s, int e, int idx, int qs, int qe, T val){
        if(qs<=s && e<=qe){
            rem(seg[idx],val);
            return;
        }
        if(s>qe || e<qs)
            return;
        int mid = (s+e)/2;
        push(seg[idx],seg[idx*2],seg[idx*2+1],mid-s+1,e-mid);
        update2(s,mid,idx*2,qs,qe,val);
        update2(mid+1,e,idx*2+1,qs,qe,val);
        seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
    }

    // add to all i (l<=i && i<=r) += val
    void update2(int l, int r, T val){
        update2(1,N,1,l,r,val);
    }

    void query(int s, int e, int idx, int ans[]){
        if(s==e){
            ans[s-1] = seg[idx].val;
            return;
        }
        int mid = (s+e)/2;
        push(seg[idx],seg[idx*2],seg[idx*2+1],mid-s+1,e-mid);
        query(s,mid,idx*2,ans);
        query(mid+1,e,idx*2+1,ans);
    }

    void query(int ans[]){
        query(1,N,1,ans);
    }

};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SEGTREE<int> seg;
    seg.init(n);

    int i;
    for(i=0;i<k;i++){
        //cout<<op[i]<<" "<<left[i]+1<<" "<<right[i]+1<<" "<<height[i]<<endl;
        if(op[i]==1){
            seg.update1(left[i]+1,right[i]+1,height[i]);
        }
        else
            seg.update2(left[i]+1,right[i]+1,height[i]);
    }

    seg.query(finalHeight);



}

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