Submission #1026723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026723		dozer	벽 (IOI14_wall)	C++14	100 / 100	1279 ms	104700 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define sp " "
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt","w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define mid (l + r) / 2
#define ll long long
#define MAXN 2000005

const int modulo = 1e9 + 7;
const ll INF = 2e18 +7;


pii mini[4 * MAXN], maks[4 * MAXN];


vector<int> v = {1, 2};
vector<int> child = {0, 0};

void push(int node, int l, int r){
  if (l == r) return;
  v[0] = 1, v[1] = 2;

  if (maks[node].nd > mini[node].nd) swap(v[0], v[1]);
  
  child[0] = LL, child[1] = RR;

  for (auto i : v){
    int type = i;
    int val = maks[node].st, time = maks[node].nd;
    if (type == 2) val = mini[node].st, time = mini[node].nd;
    for (auto gh : child){
      if (type == 1){ // max
        if (maks[gh].st <= val){
          maks[gh] = {val, time};
          if (mini[gh].st <= val)
            mini[gh] = maks[gh];
        }
      }

      else{
        if (mini[gh].st >= val){
          mini[gh] = {val, time};
          if (maks[gh].st >= val){
            maks[gh] = mini[gh];
          }
        }
      }
      //cout<<"pushed : "<<maks[gh].st<<sp<<mini[gh].st<<endl;
    }
  }

  mini[node] = {modulo, 0};
  maks[node] = {0, 0};
}

void build(int node, int l, int r){
  maks[node] = {0, 0};
  mini[node] = {modulo, 0};
  if (l == r) return;
  build(LL, l, mid);
  build(RR, mid + 1, r);
}


void update(int node, int l, int r, int sl, int sr, int val, int time, int type){
  if (l > sr || r < sl) return;
  if (l != r) push(node, l, r);
  if (l >= sl && r <= sr){
    if (type == 1){ //max operation
      if (maks[node].st <= val){
        maks[node] = {val, time};
        if (mini[node].st <= val) mini[node] = maks[node];
      }
    }
    else{
      if (mini[node].st >= val){
        mini[node] = {val, time};
        if (maks[node].st >= val) maks[node] = mini[node];
      }
    }
    return;
  }

  if (sl <= mid) update(LL, l, mid, sl, sr, val, time, type);
  if (sr > mid) update(RR, mid + 1, r, sl, sr, val, time, type);
}



int query(int node, int l, int r, int sl){
  if (l != r) push(node, l, r);
  if (l == r) {
    return maks[node].st;
  }
  if (sl <= mid) return query(LL, l, mid, sl);
  return query(RR, mid + 1, r, sl);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  build(1, 1, n);
  
  for (int i = 0; i < k; i++){
    left[i]++, right[i]++;
    update(1, 1, n, left[i], right[i], height[i], i, op[i]);
  }

  for (int j = 1; j <= n; j++){
    finalHeight[j - 1] = query(1, 1, n, j);
  } 
}

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