Submission #1211881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211881		LIA	Wall (IOI14_wall)	C++17	0 / 100	96 ms	8008 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
vll h;
ll n;
/*
void t1(ll l ,ll r, ll hi) {
  loop(i,l,r+1) {
    h[i] = max(h[i], hi);
  }
}


void t2(ll l ,ll r, ll hi) {
  loop(i,l,r+1) {
    h[i] = min(h[i], hi);
  }
}
*/

struct Seg {
  vll seg;
  ll sz = 1;
  vpll set_val;
  Seg() {
    for (; sz < n; sz *= 2);
    seg.resize(2*sz);
    set_val.resize(2*sz, {0,0}); // {the val, the type}
  }
  void push(ll node) {
    // אם זה עלה (index מחוץ לטווח הבניית עץ הפנימי), לא מעבירים הלאה ואינם מאפסים
    if (node >= sz) return;

    if (set_val[node].second == 1) {
      ll child = node * 2;
      set_val[child].first  = max(set_val[child].first,  set_val[node].first);
      set_val[child].second = 1;
      child = node * 2 + 1;
      set_val[child].first  = max(set_val[child].first,  set_val[node].first);
      set_val[child].second = 1;
    }
    if (set_val[node].second == 2) {
      ll child = node * 2;
      set_val[child].first  = min(set_val[child].first,  set_val[node].first);
      set_val[child].second = 2;
      child = node * 2 + 1;
      set_val[child].first  = min(set_val[child].first,  set_val[node].first);
      set_val[child].second = 2;
    }
    // מאפסים את התגית באותו צומת לאחר ההעברה
    set_val[node].first  = 0;
    set_val[node].second = 0;
  }

  void update(ll l, ll r, ll tl, ll tr, ll i, ll type, ll val) {
    if (tl > r || tr < l) return;
    push(i);
    if (tl >= l && tr <= r) {
      if (type == 1) {
        set_val[i].first  = max(set_val[i].first, val);
        set_val[i].second = 1;
      } else {
        set_val[i].first  = min(set_val[i].first, val);
        set_val[i].second = 2;
      }
      push(i);
      return;
    }
    ll mid = (tl + tr) / 2;
    update(l, r, tl,     mid,   i*2,   type, val);
    update(l, r, mid+1,  tr,    i*2+1, type, val);
  }

  ll query(ll i, ll l, ll r, ll idx) {
    push(i);
    if (l == r) {
      return set_val[i].first;
    }
    ll mid = (l + r) / 2;
    if (idx <= mid) {
      return query(i*2,     l,    mid, idx);
    } else {
      return query(i*2+1, mid+1,  r,   idx);
    }
  }
};

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  n = N;
  Seg seg;
  loop(i,0,k) {
    ll l  = left[i];
    ll r  = right[i];
    ll hi = height[i];
    if (op[i] == 1) {
      seg.update(l, r, 0, n-1, 1, 1, hi);
    } else {
      seg.update(l, r, 0, n-1, 1, 2, hi);
    }
  }

  loop(i,0,n) {
    finalHeight[i] = seg.query(1, 0, n-1, i);
  }
}

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