oj.uz

Submission #1108298

# Submission time Handle Problem Language Result Execution time Memory
1108298 2024-11-03T17:12:42 Z Ariadna Wall (IOI14_wall) C++14
24 / 100
 359 ms 21816 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

struct Segtree {
    int n; 
    vector<int> add, rem;
    Segtree(int n): n(n), add(vector<int>(4*n, 0)), rem(vector<int>(4*n, 1e9)) {}

    void Add(int p, int l, int r, int i, int j, int k) {
        if (i > j) return;
        push(p, l, r);
        if (i == l && j == r) {
            add[p] = max(add[p], k); 
        } else {
            int m = (l+r)/2;
            Add(2*p, l, m, i, min(m, j), k);
            Add(2*p+1, m+1, r, max(i, m+1), j, k);
            add[p] = min(add[2*p], add[2*p+1]); 
        }
    }

    void Remove(int p, int l, int r, int i, int j, int k) {
        if (i > j) return;
        push(p, l, r);
        if (i == l && j == r) {
            rem[p] = min(rem[p], k); 
        } else {
            int m = (l+r)/2;
            Remove(2*p, l, m, i, min(m, j), k);
            Remove(2*p+1, m+1, r, max(i, m+1), j, k);
            rem[p] = max(rem[2*p], rem[2*p+1]); 
        }
    }

    void push(int p, int l, int r) {
        if (l != r) {
            add[2*p] = max(add[2*p], add[p]);
            add[2*p+1] = max(add[2*p+1], add[p]);
            rem[2*p] = min(rem[2*p], rem[p]);
            rem[2*p+1] = min(rem[2*p+1], rem[p]);
        }
    }

    int get(int p, int l, int r, int i) {
        push(p, l, r);
        if (l == r) return min(rem[p], add[p]);
        int m = (l+r)/2;
        if (i <= m) return get(2*p, l, m, i);
        return get(2*p+1, m+1, r, i);
    }
};

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

    for (int i = 0; i < k; ++i) {
        if (op[i] == 1)
            St.Add(1, 0, n-1, left[i], right[i], height[i]);
        else 
            St.Remove(1, 0, n-1, left[i], right[i], height[i]);
    }

    for (int i = 0; i < n; ++i) finalHeight[i] = St.get(1, 0, n-1, i);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 2 ms 336 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 336 KB Output is correct
2 Correct 87 ms 13852 KB Output is correct
3 Correct 133 ms 8008 KB Output is correct
4 Correct 359 ms 21320 KB Output is correct
5 Correct 234 ms 21816 KB Output is correct
6 Correct 233 ms 20180 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 2 ms 336 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 336 KB Output is correct
2 Incorrect 2 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -