제출 #46861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46861		OneSubmissionMan	벽 (IOI14_wall)	C++11	61 / 100	634 ms	219276 KiB

wall

# include <bits/stdc++.h>

# define x first    
# define y second
# define mp make_pair
// everything go according to my plan      
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector         
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right  

using namespace std;

typedef pair <int, int> pii; 
typedef long long ll;
typedef long double ld;

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul

struct segtree {
  int n;
  int mx[Sz], mn[Sz];     
  int add[Sz];
  segtree (int n) : n(n) {
    memset (add, -1, sizeof add); 
  }
  void push (int v, int tl, int tr) {
    if (add[v] < 0)
      return;
    if (tl != tr) {
      add[2*v] = add[v];
      add[2*v + 1] = add[v];
    }
    mn[v] = mx[v] = add[v];
    add[v] = -1;
  }                
  int l, r, h, tp;         
  void update (int a, int b, int c, int d) {
    l = a, 
    r = b, 
    h = c,
    tp = d;
    update (1, 1, n);
  }   
  void update (int v, int tl, int tr) {
    
    push (v, tl, tr);

    if (tr < l || tl > r)
      return;

    if ((tp == 1 && mn[v] >= h) || (tp == 2 && mx[v] < h))
      return;

    if (l <= tl && tr <= r && ((tp == 1 && mx[v] <= h) || (tp == 2 && mn[v] >= h))) {
      add[v] = h;
      push (v, tl, tr);
      return;
    }
    int tmid = (tl+tr) >> 1;
    update (2*v, tl, tmid);
    update (2*v + 1, tmid+1, tr);
    recalc (v);
  }   
  void recalc (int v) {
    mx[v] = max (mx[2*v], mx[2*v + 1]);

    mn[v] = min (mn[2*v], mn[2*v + 1]);
  }
  void get (int v, int tl, int tr, int ans[]) {
    push (v, tl, tr);
    if (tl == tr) {
      ans[tl - 1] = mn[v];
      return;
    }
    int tmid = (tl+tr) >> 1;
    get (2*v, tl, tmid, ans);
    get (2*v + 1, tmid+1, tr, ans);
  }
  void get (int ans[]) {
    get (1, 1, n, ans);
  }   
};

void buildWall (int n, int k, int tp[], int l[], int r[], int h[], int ans[]) {
  segtree T (n);  
  for (int i = 0; i < k; i++) {
    //break;
    l[i]++, r[i]++;  
    T.update (l[i], r[i], h[i], tp[i]);
  }                      
  T.get (ans);
}

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