oj.uz

Submission #260677

# Submission time Handle Problem Language Result Execution time Memory
260677 2020-08-10T17:39:35 Z A02 Wall (IOI14_wall) C++14
24 / 100
 328 ms 20344 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 178 ms 10232 KB Output is correct
3 Correct 128 ms 7672 KB Output is correct
4 Correct 328 ms 13816 KB Output is correct
5 Correct 228 ms 20344 KB Output is correct
6 Correct 230 ms 18756 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -