Submission #842616

#	Time	Username	Problem	Language	Result	Execution time	Memory
842616		WLZ	Wall (IOI14_wall)	C++17	100 / 100	1247 ms	219812 KiB

wall

#include "wall.h"
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int, int> ii;
enum state {
    BUILD, DESTROY
};

struct node {
    int i, j;
    node *left, *right;
    int max_height, min_height;
    int lazy_u, lazy_d;

    void combine(int h, state op) {
        if (h == -1) return;
                
        if (op == BUILD) {
            this->lazy_u = max(this->lazy_u, h);
            if (h > this->lazy_d && this->lazy_d != -1) {
                this->lazy_d = h;
            }
        } else if (op == DESTROY) {
            if (this->lazy_d == -1) {
                this->lazy_d = h;
            } else {
                this->lazy_d = min(this->lazy_d, h);
            }
            if (h < this->lazy_u) {
                this->lazy_u = h;
            }
        }
    }
};

node *build(int i, int j) {
    if (i == j) {
        return new node{i, j, NULL, NULL, 0, 0, -1, -1};
    }
    node *left = build(i, (i + j) / 2);
    node *right = build((i + j) / 2 + 1, j);
    return new node{i, j, left, right, 0, 0, -1, -1};
}

void propagate(node *cur) {
    /* update current node */
    if (cur->lazy_u != -1) {
        cur->max_height = max(cur->max_height, cur->lazy_u);
        cur->min_height = max(cur->min_height, cur->lazy_u);
    }
    if (cur->lazy_d != -1) {
        cur->min_height = min(cur->min_height, cur->lazy_d);
        cur->max_height = min(cur->max_height, cur->lazy_d);
    }
    /* update child */
    if (cur->left != NULL) {
        cur->left->combine(cur->lazy_u,BUILD);
        cur->left->combine(cur->lazy_d,DESTROY);
        cur->right->combine(cur->lazy_u,BUILD);
        cur->right->combine(cur->lazy_d,DESTROY);
    }
    cur->lazy_d = cur->lazy_u = -1;
}

int query(node *cur, int i) {
    propagate(cur);
    if (cur->j < i || cur->i > i) return 0;
    if (cur->i == i && cur->j == i) {
        return cur->max_height;
    }
    return query(cur->left, i) + query(cur->right, i);
}

void update(state op, int i, int j, int h, node *cur) {
    propagate(cur);
    if (cur->j < i || cur->i > j) {
        return;
    }
    if (cur->i >= i && cur->j <= j) {
        cur->combine(h, op);        
        return;
    }
    update(op, i, j, h, cur->left);
    update(op, i, j, h, cur->right);
    if (op == BUILD) {
        cur->max_height = max(cur->max_height, h);
        cur->min_height = max(cur->min_height, h);
    }
    if (op == DESTROY) {
        cur->max_height = min(cur->max_height, h);
        cur->min_height = min(cur->min_height, h);
    }
    return;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    node *root = build(0, n - 1);
    for (int i = 0 ; i < k; i++) {
        if (op[i] == 1) {
            update(BUILD, left[i], right[i], height[i], root);
        } else if (op[i] == 2) {
            update(DESTROY, left[i], right[i], height[i], root);
        }
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = query(root, i);
    }
    return;
}

/*int main() {
    int n, k;
	scanf("%d %d", &n, &k);
    //int op[5], left[5], right[5], height[5];
    int *op, *left, *right, *height;
    op = (int *) malloc (sizeof (int) * 500005);
    left = (int *) malloc (sizeof (int) * 500005);
    right = (int *) malloc (sizeof (int) * 500005);
    height = (int *) malloc (sizeof (int) * 500005);
	//int op[500005], left[500005], right[500005], height[500005];
	for (int i = 0; i < k; i++) {
		scanf("%d %d %d %d",op+i,&left[i], &right[i], &height[i]);
	}
	int *finalHeight = (int *) malloc (sizeof (int) * 2000005);
	buildWall(n, k, op, left, right, height, finalHeight);
	for (int i = 0; i < n; i++) {
		printf("%d\n", finalHeight[i]);
	}
	return 0;
}*/

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