Submission #227982

#	Time	Username	Problem	Language	Result	Execution time	Memory
227982		quocnguyen1012	Wall (IOI14_wall)	C++14	100 / 100	1305 ms	110584 KiB

wall

#ifndef LOCAL
#include "wall.h"
#endif // LOCAL

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array
#define lc id << 1
#define rc id << 1 | 1

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e6 + 5, mod = 1e9 + 7, inf = 1e9;;

int N;
int mx[4 * maxn],mn[4 * maxn];
int lzmin[4 * maxn], lzmax[4 * maxn];
int res[maxn];

void build(int id, int l, int r)
{
  lzmin[id] = inf;
  lzmax[id] = -inf;
  if(l == r) return;
  int mid = (l + r) / 2;
  build(lc, l, mid); build(rc, mid + 1, r);
}

void push(int id, int l, int r)
{
  mn[id] = min(mn[id], lzmin[id]);
  mn[id] = max(mn[id], lzmax[id]);
  mx[id] = max(mx[id], lzmax[id]);
  mx[id] = min(mx[id], lzmin[id]);
  if(l != r){
    lzmin[lc] = min(lzmin[lc], lzmin[id]);
    lzmin[rc] = min(lzmin[rc], lzmin[id]);
    lzmin[lc] = max(lzmin[lc], lzmax[id]);
    lzmin[rc] = max(lzmin[rc], lzmax[id]);


    lzmax[rc] = max(lzmax[rc], lzmax[id]);
    lzmax[lc] = max(lzmax[lc], lzmax[id]);
    lzmax[rc] = min(lzmax[rc], lzmin[id]);
    lzmax[lc] = min(lzmax[lc], lzmin[id]);

    lzmax[id] = -inf; lzmin[id] = inf;
  }
}

void modify(int L, int R, int val, int type, int id = 1, int l = 1, int r = N)
{
  push(id, l, r);
  if(R < l || r < L) return;
  if(L <= l && r <= R){
    if(type == 1){
      lzmin[id] = max(lzmin[id], val);
      lzmax[id] = max(lzmax[id], val);
    }
    else if(type == 2){
      lzmin[id] = min(lzmin[id], val);
      lzmax[id] = min(lzmax[id], val);
    }
    push(id, l, r);
    return;
  }
  int mid = (l + r) / 2;
  modify(L, R, val, type, lc, l, mid); modify(L, R, val, type, rc, mid + 1, r);
  mx[id] = max(mx[lc], mx[rc]);
  mn[id] = min(mn[lc], mn[rc]);
}

void comp(int id, int l, int r)
{
  push(id, l, r);
  if(l == r){
    assert(mx[id] == mn[id]);
    res[l] = mx[id];
    return;
  }
  int mid = (l + r) / 2;
  comp(lc, l, mid); comp(rc, mid + 1, r);
}

void buildWall(int _N, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  N = _N;
  build(1, 1, N);
  for(int i = 0; i < k; ++i){
    modify(left[i] + 1, right[i] + 1, height[i], op[i]);
  }
  comp(1, 1, N);
  for(int i = 1; i <= N; ++i)
    finalHeight[i - 1] = res[i];
}
#ifdef LOCAL
signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int tc; cin >> N >> tc;
  build(1, 1, N);
  while(tc--){
    int le, ri, op, h;
    cin >> op >> le >> ri >> h;
    modify(le + 1, ri + 1, h, op);
  }
  comp(1, 1, N);
  for(int i = 1; i <= N; ++i)
    cout << res[i] << ' ';
}
#endif

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