제출 #828921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
828921		beaconmc	Wall (IOI14_wall)	C++14	100 / 100	501 ms	135208 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

const ll N = 1<<21;
ll tree[2*N];
ll mini[2*N];
ll maxi[2*N];

void prop(ll k){

  if (mini[k] <= maxi[k*2]){
    mini[k*2] = mini[k];
    maxi[k*2] = mini[k];
  }else{
    mini[k*2] = min(mini[k*2], mini[k]);
  }
  if (maxi[k] >= mini[k*2]){
    mini[k*2] = maxi[k];
    maxi[k*2] = maxi[k];
  }else{
    maxi[k*2] = max(maxi[k*2], maxi[k]);
  }

  if (mini[k] <= maxi[k*2+1]){
    mini[k*2+1] = mini[k];
    maxi[k*2+1] = mini[k];
  }else{
    mini[k*2+1] = min(mini[k*2+1], mini[k]);
  }
  if (maxi[k] >= mini[k*2+1]){
    mini[k*2+1] = maxi[k];
    maxi[k*2+1] = maxi[k];
  }else{
    maxi[k*2+1] = max(maxi[k*2+1], maxi[k]);
  }
  maxi[k] = -1;
  mini[k] = 1000000000000;
}

void updmax(ll a, ll b, ll val, ll k=1, ll x=0, ll y = N-1){
  if (b<x || a>y) return;

  if (a<=x && y<=b){
    if (val >= mini[k]){
      mini[k] = val;
      maxi[k] = val;
    }else{
      maxi[k] = max(maxi[k], val);
    }
    return;
  }
  prop(k);
  ll mid = (x+y)/2;
  updmax(a, b, val, k*2, x, mid);
  updmax(a, b, val, k*2+1, mid+1, y);
}

void updmin(ll a, ll b, ll val, ll k=1, ll x=0, ll y = N-1){
  if (b<x || a>y) return;

  if (a<=x && y<=b){
    if (val <= maxi[k]){
      mini[k] = val;
      maxi[k] = val;
    }else{
      mini[k] = min(mini[k], val);
    }
    return;
  }
  prop(k);
  ll mid = (x+y)/2;

  updmin(a, b, val, k*2, x, mid);
  updmin(a, b, val, k*2+1, mid+1, y);
}



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  FOR(i,0,2*N){
    tree[i] = 0;
    mini[i] = 1000000000000;
    maxi[i] = -1;
  }
  FOR(i,0,k){
    if (op[i] == 1){
      updmax(left[i], right[i], height[i]);
    }else{
      updmin(left[i], right[i], height[i]);
    }
  }
  FOR(i,0,N){
    prop(i);
  }

  FOR(i,0,n){
    finalHeight[i] = min((ll) finalHeight[i], mini[N+i]);
    finalHeight[i] = max((ll) finalHeight[i], maxi[N+i]);
  }
}

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