Submission #666595

#	Time	Username	Problem	Language	Result	Execution time	Memory
666595		atigun	Wall (IOI14_wall)	C++11	100 / 100	662 ms	79688 KiB

wall

#include<bits/stdc++.h>
#include"wall.h"

using namespace std;
typedef long long ll;

struct segtree{
  struct node{
    int min_opt, max_opt;
    node() : min_opt(1e9), max_opt(0){}
  };
  vector<node> tree;
  int N;
  segtree(const int& treesize) : N(treesize){
    tree.resize(4*N+5);
  }
  void push(int v, bool side){
    int where = (side ? v*2+1 : v*2);
    if(tree[v].min_opt != 1e9){
      tree[where].min_opt = min(tree[where].min_opt, tree[v].min_opt);
      tree[where].max_opt = min(tree[where].max_opt, tree[where].min_opt);
      if(side)
        tree[v].min_opt = 1e9;
    }
    if(tree[v].max_opt != 0){
      tree[where].max_opt = max(tree[where].max_opt, tree[v].max_opt);
      tree[where].min_opt = max(tree[where].min_opt, tree[where].max_opt);
      if(side)
        tree[v].max_opt = 0;
    }
  }
  void max_update(int v, int l, int r, int L, int R, int D){
    if(l > R || r < L){
      return;
    }
    if(r <= R && l >= L){
      tree[v].max_opt = max(tree[v].max_opt, D);
      tree[v].min_opt = max(tree[v].min_opt, tree[v].max_opt);
      return;
    }
    push(v, 0);
    push(v, 1);
    int mid = (l+r)/2;
    max_update(v*2, l, mid, L, R, D);
    max_update(v*2+1, mid+1, r, L, R, D);
  }
  void min_update(int v, int l, int r, int L, int R, int D){
    if(l > R || r < L){
      return;
    }
    if(r <= R && l >= L){
      tree[v].min_opt = min(tree[v].min_opt, D);
      tree[v].max_opt = min(tree[v].max_opt, tree[v].min_opt);
      return;
    }
    push(v, 0);
    push(v, 1);
    int mid = (l+r)/2;
    min_update(v*2, l, mid, L, R, D);
    min_update(v*2+1, mid+1, r, L, R, D);
  }
  void max_update(int L, int R, int D){
    max_update(1, 0, N, L, R, D);
  }
  void min_update(int L, int R, int D){
    min_update(1, 0, N, L, R, D);
  }
  int get(int v, int l, int r, int I){
    if(l == r)
      return max(min(0, tree[v].min_opt), tree[v].max_opt);
    push(v, 0);
    push(v, 1);
    int mid = (l+r)/2;
    if(I <= mid)
      return get(v*2, l, mid, I);
    else
      return get(v*2+1, mid+1, r, I);
  }
  int operator[](int I){
    return get(1, 0, N, I);
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  segtree ST(n);
  for(int i = 0; i < k; i++){
    if(op[i] == 1){
      ST.max_update(left[i], right[i], height[i]);
    } else{
      ST.min_update(left[i], right[i], height[i]);
    }
  }
  for(int i = 0; i < n; i++)
    finalHeight[i] = ST[i];
}

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