oj.uz

답안 #734109

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734109 2023-05-01T16:57:25 Z Julto 벽 (IOI14_wall) C++14
0 / 100
 159 ms 12884 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

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

void pushdown(int v, int l, int r){
    if(tree[v].type == 1){
        tree[v].mn = tree[v].level;
        tree[v].mx = max(tree[v].mn, tree[v].mx);
    }
    if(tree[v].type == 2){
        tree[v].mx = tree[v].level;
        tree[v].mn = min(tree[v].mn, tree[v].mx);
    }
    if(v * 2 + 2 < 8000105){
        if(tree[v].type == 1){
            if((tree[v * 2 + 1].type != 0 && tree[v * 2 + 1].level < tree[v].level) || tree[v * 2 + 1].mn < tree[v].level){
                tree[v * 2 + 1].type = tree[v].type, tree[v * 2 + 1].level = tree[v].level;
            }
            if((tree[v * 2 + 2].type != 0 && tree[v * 2 + 2].level < tree[v].level) || tree[v * 2 + 2].mn < tree[v].level){
                tree[v * 2 + 2].type = tree[v].type, tree[v * 2 + 2].level = tree[v].level;
            }
        }
        else if(tree[v].type == 2){
            if((tree[v * 2 + 1].type != 0 && tree[v * 2 + 1].level > tree[v].level) || tree[v * 2 + 1].mx > tree[v].level){
                tree[v * 2 + 1].type = tree[v].type, tree[v * 2 + 1].level = tree[v].level;
            }
            if((tree[v * 2 + 2].type != 0 && tree[v * 2 + 2].level > tree[v].level) || tree[v * 2 + 2].mx > tree[v].level){
                tree[v * 2 + 2].type = tree[v].type, tree[v * 2 + 2].level = tree[v].level;
            }
        }
    }
    
    tree[v].type = 0, tree[v].level = 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);
    tree[v].mx = max(tree[v * 2 + 1].mx, tree[v * 2 + 2].mx);
    tree[v].mn = min(tree[v * 2 + 1].mn, tree[v * 2 + 2].mn);
}

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].mx;
        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 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 159 ms 12884 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 4 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

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