Submission #62454

#	Time	Username	Problem	Language	Result	Execution time	Memory
62454		evpipis	Wall (IOI14_wall)	C++11	100 / 100	1783 ms	205276 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

//#define TEST

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int len = 2e6, inf = 1e9;
ii tree[4*len];

void upd(ii &a, ii b){
    if (a.fi <= b.fi && b.se <= a.se)
        a = b;
    else if (b.fi < a.fi)
        a.se = min(a.se, b.se), a.fi = min(a.fi, b.se);
    else if (b.se > a.se)
        a.fi = max(a.fi, b.fi), a.se = max(a.se, b.fi);
}

void prop(int p, int l, int r){
    if (l == r) return;

    upd(tree[2*p], tree[p]);
    upd(tree[2*p+1], tree[p]);
    tree[p] = mp(0, inf);
}

void update(int p, int l, int r, int i, int j, ii val){
    prop(p, l, r);
    if (r < i || j < l)
        return;
    if (i <= l && r <= j)
        upd(tree[p], val);
    else{
        int mid = (l+r)/2;
        update(2*p, l, mid, i, j, val);
        update(2*p+1, mid+1, r, i, j, val);
    }
}

int query(int p, int l, int r, int i){
    prop(p, l, r);
    if (l == r)
        return tree[p].fi;

    int mid = (l+r)/2;
    if (i <= mid)
        return query(2*p, l, mid, i);
    return query(2*p+1, mid+1, r, i);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < 4*n; i++)
        tree[i] = mp(0, inf);

    for (int i = 0; i < k; i++){
        ii val;
        int t = op[i], l = left[i], r = right[i], h = height[i];
        if (t == 1)
            val = mp(h, inf);
        else
            val = mp(0, h);

        update(1, 0, n-1, l, r, val);
    }

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

#ifdef TEST
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;
}
#endif

/*
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