Submission #733530

#	Time	Username	Problem	Language	Result	Execution time	Memory
733530		Julto	벽 (IOI14_wall)	C++14	0 / 100	140 ms	13988 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

struct Node{
	int type, level;
} tree[8000105];

void pushdown(int v, int l, int r){
    int mid = (l + r) / 2;
    if(v * 2 + 2 < 8000105){
        if(tree[v].type == 1){
            if(tree[v * 2 + 1].level < tree[v].level || (tree[v * 2 + 1].type == 0 && l != mid - 1)){
                tree[v * 2 + 1] = tree[v];
            }
            if(tree[v * 2 + 2].level < tree[v].level || (tree[v * 2 + 2].type == 0 && mid != r - 1)){
                tree[v * 2 + 2] = tree[v];
            }
        }
        if(tree[v].type == 2){
            if(tree[v * 2 + 1].level > tree[v].level || (tree[v * 2 + 1].type == 0 && l != mid - 1)){
                tree[v * 2 + 1] = tree[v];
            }
            if(tree[v * 2 + 2].level > tree[v].level || (tree[v * 2 + 2].type == 0 && mid != r - 1)){
                tree[v * 2 + 2] = tree[v];
            }
            
        }
    }
    tree[v].type = 0;
}


void upd(int v, int l, int r, int lq, int rq, int t, int x){
    pushdown(v, l, r);
    if(l >= rq || lq >= r){
        return;
    }
    if(l >= lq && r <= rq){
        tree[v].type = t, tree[v].level = x;
        pushdown(v, l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(v * 2 + 1, l, mid, lq, rq, t, x);
    upd(v * 2 + 2, mid, r, lq, rq, t, x);

}

void taketree(int v, int l, int r, vector<int> &ans){
    pushdown(v, l, r);
    //cout << l << " " << r << " " << tree[v].type << " " << tree[v].level << '\n';
    if(l == r - 1){
        ans[l] = tree[v].level;
        return;
    }
    int mid = (l + r) / 2;
    
    taketree(v * 2 + 1, l, mid, ans);
    taketree(v * 2 + 2, mid, r, ans);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 0; i < k; i++){
        upd(0, 0, n, left[i], right[i] + 1, op[i], height[i]);
    }
    vector<int> ans(n);
    taketree(0, 0, n, ans);
    for(int i = 0; i < n; i++){
        finalHeight[i] = ans[i];
        //cout << ans[i] << " ";
    }
}

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