제출 #260677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260677		A02	Wall (IOI14_wall)	C++14	24 / 100	328 ms	20344 KiB

wall

#include "wall.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>

using namespace std;

int querySegTree(int n, vector<int> &tree, int p){

    int result = 0;

    for (p += n; p > 0; p /= 2){

        result = max(tree[p], result);

    }

    return result;
}

void updateSegTree(int n , vector<int> &tree, int l, int r, int t){

    l += n;
    r += n;

    for (; l < r; l /= 2, r /= 2){

        if (l % 2 == 1){
            tree[l] = max(tree[l], t);
            l++;
        }

        if (r % 2 == 1){
            tree[r - 1] = max(tree[r - 1], t);
            r--;
        }
    }

}

int querySegTree2(int n, vector<int> &tree, int p){

    int result = 100000;

    for (p += n; p > 0; p /= 2){

        result = min(tree[p], result);

    }

    return result;
}

void updateSegTree2(int n , vector<int> &tree, int l, int r, int t){

    l += n;
    r += n;

    for (; l < r; l /= 2, r /= 2){

        if (l % 2 == 1){
            tree[l] = min(tree[l], t);
            l++;
        }

        if (r % 2 == 1){
            tree[r - 1] = min(tree[r - 1], t);
            r--;
        }
    }

}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

    vector<int> max_tree (2 * n, 0);

    vector<int> min_tree (2 * n, 100000);

//
//    updateSegTree(n, max_tree, 2, 7, 10);
//    updateSegTree(n, max_tree, 3, 5, 12);
//
//    for (int i = 0; i < n; i++){
//        cout << querySegTree(n, max_tree, i) << ' ';
//    }
//    cout << endl;

    for (int i = 0; i < k; i++){
        if (op[i] == 1){
            updateSegTree(n, max_tree, left[i], right[i] + 1, height[i]);
        } else {
            updateSegTree2(n, min_tree, left[i], right[i] + 1, height[i]);
        }
    }

    for (int i = 0; i < n; i++){

        finalHeight[i] = min(querySegTree(n, max_tree, i), querySegTree2(n, min_tree, i));
        //cout << i << ' ' << querySegTree(n, max_tree, i) << ' ' << querySegTree2(n, min_tree, i) << endl;
    }


    return;
}

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