Submission #577555

#	Time	Username	Problem	Language	Result	Execution time	Memory
577555		jack715	Wall (IOI14_wall)	C++14	100 / 100	787 ms	221984 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;

struct node {
  int mn, mx, st, end;
  node* left;
  node* right;
  node(int MN, int MX, int ST, int END) {
    mn = MN, mx = MX;
    st = ST, end = END;
    left = nullptr;
    right = nullptr;
  };
};

void propogate(node* now) {
  if (now->left == nullptr)
    now->left = new node(0, 0, now->st, (now->st+now->end)/2);
  if (now->right == nullptr)
    now->right = new node(0, 0, (now->st+now->end)/2+1, now->end);
  
  if (now->mx != -1) {
    now->left->mx = max(now->left->mx, now->mx);
    now->right->mx = max(now->right->mx, now->mx);
    if (now->left->mn != -1)
      now->left->mn = max(now->left->mn, now->mx);
    if (now->right->mn != -1)
      now->right->mn = max(now->right->mn, now->mx);
    now->mx = -1;
  } 
  if (now->mn != -1) {
    if (now->left->mn != -1)
      now->left->mn = min(now->left->mn, now->mn);
    else
      now->left->mn = now->mn;

    if (now->right->mn != -1)
      now->right->mn = min(now->right->mn, now->mn);
    else 
      now->right->mn = now->mn;
    
    now->left->mx = min(now->left->mx, now->mn);
    now->right->mx = min(now->right->mx, now->mn);
    now->mn = -1;
  }
}

void update(node* now, int& l, int& r, int& v, int& t) {
  if (now->st > r || now->end < l) 
    return;
  if (l <= now->st && now->end <= r) {
    if (t == 1) {
      now->mx = max(now->mx, v);
      if (now->mn != -1)
        now->mn = max(now->mn, v);
    } else {
      if (now->mn != -1)
        now->mn = min(now->mn, v);
      else
        now->mn = v;
      now->mx = min(now->mx, v);
    }
    return;
  }

  propogate(now);
  update(now->left, l, r, v, t);
  update(now->right, l, r, v, t);
}

vector<int> ans;
void query(node* now) {
  if (now->st == now->end) {
    ans[now->st] = now->mx;
    return;
  }
  propogate(now);
  query(now->left);
  query(now->right);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  node* root = new node(0, 0, 0, n-1);

  for (int i = 0; i < k; i++) {
    update(root, left[i], right[i], height[i], op[i]); 
  }

  ans.resize(n, 0);
  query(root);
  for (int i = 0; i < n; i++)
    finalHeight[i] = ans[i];
  return;
}

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