Submission #815709

#	Time	Username	Problem	Language	Result	Execution time	Memory
815709		Liudas	Wall (IOI14_wall)	C++17	100 / 100	915 ms	59304 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#include "wall.h"
using namespace std;
class seg_tree{
public:
    struct node{
        int maxi;
        int mini;
    };
    vector<node> tree;
    int N;
    node em = {0, INT_MAX};
    seg_tree(int K){
        N = 1;
        while(N <= K){
            N *= 2;
        }
        tree.assign(N * 2, em);
    }
    node apply(node a, node b){
        node c = a;
        c.maxi = min(max(a.maxi, b.maxi), b.mini);
        c.mini = min(max(a.mini, b.maxi), b.mini);
        return c;
    }
    void propogate(int head, int L, int R){
        if(R - L == 1)return;
        tree[head * 2 + 1] = apply(tree[head * 2 + 1], tree[head]);
        tree[head * 2 + 2] = apply(tree[head * 2 + 2], tree[head]);
        tree[head] = em;
    }
    void mod(int head, int l, int r, int L, int R, int v1, int v2){
        propogate(head, L, R);
        if(l <= L && R <= r){
            if(v2){
                tree[head].maxi = max(tree[head].maxi, v1);
                tree[head].mini = max(tree[head].mini, v1);
            }
            else{
                tree[head].mini = min(tree[head].mini, v1);
                tree[head].maxi = min(tree[head].maxi, v1);
            }
            return;
        }
        if(R <= l || L >= r){
            return;
        }
        int mid = (L + R) / 2;
        mod(head * 2 + 1, l, r, L, mid, v1, v2);
        mod(head * 2 + 2, l, r, mid, R, v1, v2);
    }
    void mod(int v1, int v2, int l, int r){
        mod(0, l, r, 0, N, v1, v2);
    }
    int get(int head, int L, int R, int pos){
        propogate(head, L, R);
        if(R-L == 1){
            return min(tree[head].maxi, tree[head].mini);
        }
        int mid = (L + R) / 2;
        int ans;
        if(pos < mid){
            ans = get(head * 2 + 1, L, mid, pos);
        }
        else{
            ans = get(head * 2 + 2, mid, R, pos);
        }
        return ans;
    }
    int get(int pos){
        return get(0, 0, N, pos);
    }
};
void buildWall(int N, int K, int op[], int l[], int r[], int h[], int fh[]){
    seg_tree tree(N);
    for(int i = 0; i < K; i ++){
        int OP = op[i], L = l[i], R = r[i], H = h[i];
        if(OP == 1){
            tree.mod(H, 1, L, R + 1);
        }
        else{
            tree.mod(H, 0, L, R + 1);
        }
    }
    for(int i = 0; i < N; i ++){
        fh[i] = tree.get(i);
    }
}

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