Submission #577540

#	Time	Username	Problem	Language	Result	Execution time	Memory
577540		jack715	Wall (IOI14_wall)	C++14	61 / 100	925 ms	262144 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second

using namespace std;

vector<vector<int> > segtree;

void propogate(int indx) {
  if (segtree[indx][0] != -1) {
    segtree[indx*2][0] = max(segtree[indx*2][0], segtree[indx][0]);
    segtree[indx*2+1][0] = max(segtree[indx*2+1][0], segtree[indx][0]);
    if (segtree[indx*2][1] != -1)
      segtree[indx*2][1] = max(segtree[indx*2][1], segtree[indx][0]);
    if (segtree[indx*2+1][1] != -1)
      segtree[indx*2+1][1] = max(segtree[indx*2+1][1], segtree[indx][0]);
    segtree[indx][0] = -1;
  } 
  if (segtree[indx][1] != -1) {
    if (segtree[indx*2][1] != -1)
      segtree[indx*2][1] = min(segtree[indx*2][1], segtree[indx][1]);
    else
      segtree[indx*2][1] = segtree[indx][1];

    if (segtree[indx*2+1][1] != -1)
      segtree[indx*2+1][1] = min(segtree[indx*2+1][1], segtree[indx][1]);
    else 
      segtree[indx*2+1][1] = segtree[indx][1];
    
    segtree[indx*2][0] = min(segtree[indx*2][0], segtree[indx][1]);
    segtree[indx*2+1][0] = min(segtree[indx*2+1][0], segtree[indx][1]);
    segtree[indx][1] = -1;
  }
}

void update(int indx, int st, int end, int l, int r, int v, int t) {
  if (st > r || end < l) 
    return;
  if (l <= st && end <= r) {
    if (t == 1) {
      segtree[indx][0] = max(segtree[indx][0], v);
      if (segtree[indx][1] != -1)
        segtree[indx][1] = max(segtree[indx][1], v);
    } else {
      if (segtree[indx][1] != -1)
        segtree[indx][1] = min(segtree[indx][1], v);
      else
        segtree[indx][1] = v;
      segtree[indx][0] = min(segtree[indx][0], v);
    }
    return;
  }

  propogate(indx);
  int mid = (st + end) / 2;
  update(indx*2, st, mid, l, r, v, t);
  update(indx*2+1, mid+1, end, l, r, v, t);
}

int query(int indx, int st, int end, int v) {
  if (st == end) {
    // cout << indx << ' ' << segtree[indx][0] << ' ' << segtree[indx][1] << '\n';
    return segtree[indx][0];
  }
  propogate(indx);

  int mid = (st + end) / 2;
  if (v <= mid)
    return query(indx*2, st, mid, v);
  return query(indx*2+1, mid+1, end, v);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  segtree.resize(n*4+5, {0, 0});
 
  for (int i = 0; i < k; i++) {
    update(1, 0, n-1, left[i], right[i], height[i], op[i]); 
  }

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

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