oj.uz

답안 #733530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
733530 2023-05-01T02:18:10 Z Julto 벽 (IOI14_wall) C++14
0 / 100
 140 ms 13988 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 140 ms 13988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 448 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -