제출 #287125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
287125		Atill83	벽 (IOI14_wall)	C++14	8 / 100	3078 ms	8192 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;

struct node{
    int deg = 0;
    node * l = NULL; 
    node * r = NULL;
};
typedef node * pn;

void upd(pn cur, int tl, int tr, int ll, int rr, int dg, int op){
    //cerr<<ll<<" "<<rr<<" "<<cur->deg<<endl;
    if(ll > rr) return;
    if(tl == ll && tr == rr){
        if(cur->l == NULL){
            if(op == 1){
                cur->deg = max(cur->deg, dg);
            }else{
                cur->deg = min(cur->deg, dg);
            }
        }else{
            assert((cur->r) != NULL);
            int tm = (tl + tr) / 2;
            upd(cur->l, tl, tm, ll, tm, dg, op);
            upd(cur->r, tm + 1, tr, tm + 1, rr, dg, op);
        }
    }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;
        }
        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{
        assert(cur->r != NULL);
        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: 8 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39