oj.uz

Submission #880510

# Submission time Handle Problem Language Result Execution time Memory
880510 2023-11-29T14:55:44 Z Mr_Husanboy Wall (IOI14_wall) C++17
100 / 100
 563 ms 94800 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){
        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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 900 KB Output is correct
6 Correct 4 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 110 ms 13140 KB Output is correct
3 Correct 123 ms 7440 KB Output is correct
4 Correct 364 ms 20092 KB Output is correct
5 Correct 225 ms 20304 KB Output is correct
6 Correct 229 ms 19052 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 560 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 4 ms 1112 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 111 ms 12656 KB Output is correct
9 Correct 135 ms 7508 KB Output is correct
10 Correct 351 ms 19644 KB Output is correct
11 Correct 230 ms 20048 KB Output is correct
12 Correct 213 ms 19028 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 111 ms 12800 KB Output is correct
15 Correct 23 ms 1964 KB Output is correct
16 Correct 381 ms 19844 KB Output is correct
17 Correct 221 ms 19212 KB Output is correct
18 Correct 226 ms 19276 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 856 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 114 ms 13156 KB Output is correct
9 Correct 129 ms 7248 KB Output is correct
10 Correct 349 ms 19724 KB Output is correct
11 Correct 233 ms 19908 KB Output is correct
12 Correct 227 ms 19024 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 129 ms 12884 KB Output is correct
15 Correct 20 ms 2128 KB Output is correct
16 Correct 347 ms 19800 KB Output is correct
17 Correct 233 ms 19280 KB Output is correct
18 Correct 251 ms 19236 KB Output is correct
19 Correct 526 ms 94548 KB Output is correct
20 Correct 556 ms 94800 KB Output is correct
21 Correct 513 ms 94660 KB Output is correct
22 Correct 511 ms 94800 KB Output is correct
23 Correct 563 ms 94628 KB Output is correct
24 Correct 513 ms 94700 KB Output is correct
25 Correct 512 ms 94596 KB Output is correct
26 Correct 515 ms 94548 KB Output is correct
27 Correct 509 ms 94600 KB Output is correct
28 Correct 510 ms 92024 KB Output is correct
29 Correct 504 ms 91728 KB Output is correct
30 Correct 507 ms 91728 KB Output is correct