oj.uz

Submission #880388

# Submission time Handle Problem Language Result Execution time Memory
880388 2023-11-29T09:44:09 Z Mr_Husanboy Wall (IOI14_wall) C++17
0 / 100
 117 ms 12636 KB 
#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){
        mx = max(mx, x);
      }else{
        mn = min(x, mn);
        mx = min(mx, mn);
      }
    }
  };
  vector<Node> t;
  int n;

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

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

  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){
      t[x].apply(val, type); 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){
      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);
    for(int i = 0; i < k; i ++){
      t.upd(left[i], right[i], height[i], op[i]);
    }
    vector<int> an(n);
    t.finish(an);
    for(int i = 0; i < n; i ++){
      ans[i] = an[i];
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 117 ms 12636 KB Output is correct
3 Incorrect 116 ms 7248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Output is correct
2 Incorrect 1 ms 524 KB Output isn't correct
3 Halted 0 ms 0 KB -