Submission #1108303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108303		Ariadna	Wall (IOI14_wall)	C++14	100 / 100	1127 ms	89120 KiB

wall

#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); 
            rem[p] = max(add[p], rem[p]);
        } 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); 
            add[p] = min(add[p], rem[p]);
        } 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] = min(rem[p], max(add[2*p], add[p]));
            add[2*p+1] = min(rem[p], max(add[2*p+1], add[p]));
            rem[2*p] = max(add[p], min(rem[2*p], rem[p]));
            rem[2*p+1] = max(add[p], min(rem[2*p+1], rem[p]));
            add[p] = 0;
            rem[p] = 1e9;
        }
    }

    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: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39