Submission #287170

#	Time	Username	Problem	Language	Result	Execution time	Memory
287170		Atill83	Wall (IOI14_wall)	C++14	0 / 100	726 ms	19960 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
const int MAXN = (int) 2e6 + 5;
typedef pair<int, int> pii;
int * an;
const int inf = (int) 1e6;
struct node{
    int deg = 0, lazy1 = 0, lazy2 = inf;
    node * l = NULL;
    node * r = NULL;
};
typedef node * pn;

void push(pn cur){
    cur->l->deg = max(cur->l->deg, cur->lazy1);
    cur->l->deg = min(cur->l->deg, cur->lazy2);
    cur->r->deg = max(cur->r->deg, cur->lazy1);
    cur->r->deg = min(cur->r->deg, cur->lazy2);
    if(cur->lazy1 >= cur->l->lazy2){
        cur->l->lazy1 = cur->lazy1;
        cur->l->lazy2 = cur->lazy2;
    }else if(cur->lazy1 >= cur->l->lazy1){
        cur->l->lazy1 = cur->lazy1;
        cur->l->lazy2 = min(cur->l->lazy2, cur->lazy2);
    }else if(cur->lazy2 >= cur->l->lazy1){
        cur->l->lazy2 = min(cur->l->lazy2, cur->lazy2);
    }else{
        cur->l->lazy1 = cur->lazy1;
        cur->l->lazy2 = cur->lazy2;
    }

    if(cur->lazy1 >= cur->r->lazy2){
        cur->r->lazy1 = cur->lazy1;
        cur->r->lazy2 = cur->lazy2;
    }else if(cur->lazy1 >= cur->r->lazy1){
        cur->r->lazy1 = cur->lazy1;
        cur->r->lazy2 = min(cur->r->lazy2, cur->lazy2);
    }else if(cur->lazy2 >= cur->r->lazy1){
        cur->r->lazy2 = min(cur->r->lazy2, cur->lazy2);
    }else{
        cur->r->lazy1 = cur->lazy1;
        cur->r->lazy2 = cur->lazy2;
    }

    cur->lazy1 = 0;
    cur->lazy2 = inf;
}


void upd(pn cur, int tl, int tr, int ll, int rr, int dg, int op){
    if(ll > rr) return;
    if(tl == ll && tr == rr){
        if(op == 1){
            if(dg > cur->lazy2){
                cur->lazy2 = inf;
                cur->lazy1 = dg;
            }else if(dg > cur->lazy1){
                cur->lazy1 = dg;
            }
            cur->deg = max(cur->deg, dg);
        }else{
            if(dg < cur->lazy1){
                cur->lazy1 = 0;
                cur->lazy2 = dg;
            }else if(dg < cur->lazy2){
                cur->lazy2 = dg;
            }
            cur->deg = min(cur->deg, dg);
        }
    }else{
        int tm = (tl + tr) / 2;
        if(cur->l == NULL){
            cur->l = new node;
            cur->r = new node;
            cur->l->deg = cur->deg;
            cur->r->deg = cur->deg;
        }
        push(cur);
        upd(cur->l, tl, tm, ll, min(tm, rr), dg, op);
        upd(cur->r, tm + 1, tr, max(ll, tm + 1), rr, dg, op);
    }
}

void fina(pn cur, int tl , int tr){
    if(cur->l == NULL){
        for(int i = tl; i <= tr; i++){
            an[i] = cur->deg;
        }
    }else{
        push(cur);
        int tm = (tl + tr) / 2;
        fina(cur->l, tl, tm);
        fina(cur->r, tm + 1, tr);
    }
}



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    pn root = new node;
    root->deg = 0;
    an = finalHeight;
    for(int i = 0; i < k; i++){
        upd(root, 0, n - 1, left[i], right[i], height[i], op[i]);
    }
    fina(root, 0, n - 1);
    return;
}

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