IOI 2014 - Wall

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define all(x) x.begin(), x.end()
#define f(i,a,b) for(int i = (a); i <= (b); i++)
#define fd(i,a,b) for(int i = (a); i >= (b); i--)
#define mp make_pair
#define faster_io() ios_base::sync_with_stdio(false)
#define pb push_back
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
#define TRACE(x) cout << #x << " = " << x << "\n";
#define vii vector<pair<int,int>>

const ll INFLL = 100000000000000000;

// --------------------------------------------------------------------------

const int RIGHT = (1<<21);
const int SIZE = (1<<22)+5;

int D[SIZE], U[SIZE];
int N, K;

void combine(int n, int d, int u)
{
    D[n] = min(D[n], d);
    D[n] = max(D[n], u);
    U[n] = max(U[n], u);
    U[n] = min(U[n], d);
}

void process(int n, char t, int h)
{
    if(t == 'd')
    {
        D[n] = min(D[n], h);
        U[n] = min(U[n], h);
    }
    if(t == 'u')
    {
        D[n] = max(D[n], h);
        U[n] = max(U[n], h);
    }
}

void update(int l, int r, char t, int h, int n, int a, int b)
{
    if(a > r || b < l) return;
    if(a >= l && b <= r)
    {
        process(n,t,h);
        return;
    }

    combine(2*n, D[n], U[n]);
    combine(2*n+1, D[n], U[n]);
    D[n] = SIZE, U[n] = 0;

    int mid = (a+b) / 2;
    update(l,r,t,h,2*n,a,mid);
    update(l,r,t,h,2*n+1,mid+1,b);
}

void complete()
{
    f(i,1,RIGHT-1)
    {
        combine(2*i, D[i], U[i]);
        combine(2*i+1, D[i], U[i]);
    }
}

int main()
{
    scanf("%d%d", &N, &K);

    f(i,1,K)
    {
        int id, l, r, h;
        scanf("%d%d%d%d", &id, &l, &r, &h);
        char t = id==1 ? 'u' : 'd';
        update(l+1,r+1,t,h,1,1,RIGHT);
    }

    complete();
    f(i,RIGHT,RIGHT+N-1) printf("%d\n", min(D[i],U[i]));
}