Submission #880510

#	Time	Username	Problem	Language	Result	Execution time	Memory
880510		Mr_Husanboy	Wall (IOI14_wall)	C++17	100 / 100	563 ms	94800 KiB

wall

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

using namespace std;
const int inf = 1e9;



struct Segtree{
  struct Node{
    int mn = inf, mx = 0;
    void apply(int x, int type){
      if(type == 1){
        mn = max(mn, x);
        mx = max(mx, x);
      }else{
        mn = min(mn, x);
        mx = min(mx, x);
      }
    }
    void calibrate(){
      mn = inf, mx = 0;
    }
  };
  vector<Node> t;
  int n;

  void init(int _n){
    n = _n;
    t.resize(4 * n);
  }

  void push(int x){
    t[x * 2].mn = min(t[x * 2].mn, t[x].mn);
    t[x * 2].mn = max(t[x * 2].mn, t[x].mx);
    t[x * 2].mx = max(t[x * 2].mx, t[x].mx);
    t[x * 2].mx = min(t[x * 2].mx, t[x].mn);
    t[x * 2 + 1].mn = min(t[x * 2 + 1].mn, t[x].mn);
    t[x * 2 + 1].mn = max(t[x * 2 + 1].mn, t[x].mx);
    t[x * 2 + 1].mx = max(t[x * 2 + 1].mx, t[x].mx);
    t[x * 2 + 1].mx = min(t[x * 2 + 1].mx, t[x].mn);
    t[x].calibrate();
  }

  void upd(int x, int l, int r, int ql, int qr, int val, int type){
    if(l > qr || ql > r) return;
    if(ql <= l && r <= qr){
      //cout << l << ' ' << r << ' ' << val << ' ' << type << endl;

      t[x].apply(val, type);
     // cout << t[x].mx << endl;
      return;
    } 
    push(x);
    int m = (l + r) / 2;
    upd(x * 2, l, m, ql, qr, val, type);
    upd(x * 2 + 1, m + 1, r, ql, qr, val, type);
  }

  void finish(vector<int> &ans, int x, int l, int r){
    if(l == r){
      //t[x].apply(t[x].mn, 2);
      ans[l] = t[x].mx;
      return;
    }
    push(x);
    int m = (l + r) / 2;
    finish(ans, x * 2, l, m); finish(ans, x * 2 + 1, m + 1, r);
  }

  //interface

  void upd(int l, int r, int val, int type){
    upd(1, 0, n - 1, l, r, val, type);
  }

  void finish(vector<int> &ans){
    finish(ans, 1, 0, n - 1);
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[]){
    Segtree t;
    t.init(n);
    vector<int> an(n);
    for(int i = 0; i < k; i ++){
      t.upd(left[i], right[i], height[i], op[i]);
      // t.finish(an);
      // for(int j = 0; j < n; j ++)cout << an[j] << ' ';
      // cout << endl;
    }
    t.finish(an);
    for(int i = 0; i < n; i ++){
      ans[i] = an[i];
    }
}

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