oj.uz

Submission #821839

# Submission time Handle Problem Language Result Execution time Memory
821839 2023-08-11T18:43:48 Z VMaksimoski008 Wall (IOI14_wall) C++17
0 / 100
 1 ms 432 KB 
#include "wall.h"
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
#define each(x, v) for(auto &x : v)
#define mp make_pair

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

struct Node { int mx, mn; };
vector<int> ans;

struct SegTree {
    int n;
    vector<Node> tree;
    vector<Node> lazy;

    SegTree(int n) : n(n), tree(4*n+5, Node{0, 0}), lazy(4*n+5, Node{0, 0}) {}

    void push(int u, int tl, int tr) {
        //left child
        tree[2*u].mx = min(tree[2*u].mx, tree[u].mn);
        tree[2*u].mn = min(tree[2*u].mn, tree[u].mn);
        tree[2*u].mx = max(tree[2*u].mx, tree[u].mx);
        tree[2*u].mn = max(tree[2*u].mn, tree[u].mx);

        //right child
        tree[2*u+1].mx = min(tree[2*u+1].mx, tree[u].mn);
        tree[2*u+1].mn = min(tree[2*u+1].mn, tree[u].mn);
        tree[2*u+1].mx = max(tree[2*u+1].mx, tree[u].mx);
        tree[2*u+1].mn = max(tree[2*u+1].mn, tree[u].mx);
    }

    void update(int u, int tl, int tr, int l, int r, int type, int val) {
        if(tl > r || l > tr || tl > tr) return ;

        if(l <= tl && tr <= r) {
            if(type == 1) {
                tree[u].mx = max(tree[u].mx, val);
                tree[u].mn = max(tree[u].mn, val);
            } else {
                tree[u].mx = min(tree[u].mx, val);
                tree[u].mn = min(tree[u].mn, val);
            }
        }

        push(u, tl, tr);
        tree[u].mn = INT_MAX;
        tree[u].mx = 0;

        int tm = (tl + tr) / 2;
        update(2*u, tl, tm, l, r, type, val);
        update(2*u+1, tm+1, tr, l, r, type, val);
    }

    void query(int u, int tl, int tr) {
        if(tl == tr){
		    ans[tl] = tree[u].mn;
		    return;
	    }

	    push(u, tl, tr);
	    int tm = (tl + tr) / 2;
	    query(2*u, tl, tm);
	    query(2*u+1, tm+1, tr);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  SegTree tree(n);
  ans.resize(n);

  for(int i=0; i<k; i++) {
    tree.update(1, 0, n-1, left[i], right[i], op[i], height[i]);
  }

  tree.query(1, 0, n-1);

  for(int i=0; i<n; i++)
    finalHeight[i] = ans[i];

  return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -