제출 #1295296

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1295296		kantaponz	Wall (IOI14_wall)	C++20	100 / 100	554 ms	145584 KiB

wall

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;

#define ll long long

bool hasLazy[8000005];

struct SegmentTree {
    vector<int> tree[2], minLazy, maxLazy;
    

    void build(int N, int idx, int l, int r) {
        if (idx == 1) {
            tree[0].resize(4 * N);
            tree[1].resize(4 * N);
            minLazy.resize(4 * N);
            maxLazy.resize(4 * N);
            fill(tree[1].begin(), tree[1].begin() + 4 * N, 1e9);
        }
        maxLazy[idx] = 1e9;
        if (l != r) {
            int mid = (l + r) >> 1;
            build(N, idx * 2, l, mid);
            build(N, idx * 2 + 1, mid + 1, r);
        }
        return;
    }

    void push(int idx, int l, int r) {
        
        if (!hasLazy[idx]) return;

        int mid = (l + r) >> 1;

        tree[0][idx] = max(minLazy[idx], tree[0][idx]);
        tree[1][idx] = min(maxLazy[idx], tree[1][idx]);

        if (l != r) {
            
            minLazy[2*idx] = min(maxLazy[idx], max(minLazy[idx], minLazy[2*idx]));
            maxLazy[2*idx] = min(maxLazy[idx], max(minLazy[idx], maxLazy[2*idx]));

            minLazy[2*idx+1] = min(maxLazy[idx], max(minLazy[idx], minLazy[2*idx+1]));
            maxLazy[2*idx+1] = min(maxLazy[idx], max(minLazy[idx], maxLazy[2*idx+1]));
            hasLazy[2*idx+1] = hasLazy[2*idx] = 1;
        }

        hasLazy[idx] = 0;
        minLazy[idx] = 0;
        maxLazy[idx] = 1e9;//*/
    }

    void RMaxU(int idx, int l, int r, int ql, int qr, int val) {

        if (qr < l || ql > r) return;

        if (l >= ql && qr >= r) {
            maxLazy[idx] = min(maxLazy[idx], val);
            minLazy[idx] = min(minLazy[idx], val);
            hasLazy[idx] = 1;
            return;
        }
        push(idx, l, r);
        int mid = (l + r) >> 1;
        if (l != r) {
            RMaxU(idx*2, l, mid, ql, qr, val);
            RMaxU(idx*2+1, mid + 1, r, ql, qr, val);
        }//*/


    }

    void RMinU(int idx, int l, int r, int ql, int qr, int val) {
        

        if (qr < l || ql > r) return;

        if (l >= ql && qr >= r) {
            maxLazy[idx] = max(maxLazy[idx], val);
            minLazy[idx] = max(minLazy[idx], val);
            hasLazy[idx] = 1;
            return;
        }
        push(idx, l, r);
        int mid = (l + r) >> 1;
        if (l != r) {
            RMinU(idx*2, l, mid, ql, qr, val);
            RMinU(idx*2+1, mid + 1, r, ql, qr, val);
        }//*/

    }

    int query(int idx, int l, int r, int k) {
        push(idx, l, r);

        if (l == r) {
            return tree[0][idx];
        }

        int mid = (l + r) >> 1;
        if (k <= mid) {
            return query(idx*2, l, mid, k);
        } else {
            return query(idx*2+1, mid + 1, r, k);
        }
       return 0;
    }
};


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    SegmentTree seg;
    seg.build(n, 1, 0, n - 1);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            seg.RMinU(1, 0, n-1, left[i], right[i], height[i]);
        } else {
            seg.RMaxU(1, 0, n-1, left[i], right[i], height[i]);
        }
    }

    for (int i = 0; i < n; i++) {
        finalHeight[i] = seg.query(1, 0, n - 1, i);
    }

}



/*
int main()
{
  int n;
  int k;

  int i, j;  
  int status = 0;

  status = scanf("%d%d", &n, &k);
  assert(status == 2);

  int* op = (int*)calloc(sizeof(int), k);
  int* left = (int*)calloc(sizeof(int), k);
  int* right = (int*)calloc(sizeof(int), k);
  int* height = (int*)calloc(sizeof(int), k);
  int* finalHeight = (int*)calloc(sizeof(int), n);

  for (i = 0; i < k; i++){
    status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    assert(status == 4);
  }

  buildWall(n, k, op, left, right, height, finalHeight);

  for (j = 0; j < n; j++)
    printf("%d\n", finalHeight[j]);
  
  return 0;
}*/

/*

10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0


*/

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