oj.uz

Submission #151964

# Submission time Handle Problem Language Result Execution time Memory
151964 2019-09-05T17:04:17 Z erebos Wall (IOI14_wall) C++17
0 / 100
 235 ms 13944 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int inf = 1e9;
struct wall {
    int mn=0, mx=0;
};
wall operator+(wall a, wall b) {
    return {min({max({a.mn, b.mn}), b.mx}), min({max({a.mx, b.mn}), b.mx})};
}
vector<wall>tree;
void update(int node, int s, int e, int l, int r, wall diff) {
    if(e<l || r<s) return;
    if(s!=e) {
        tree[node*2]=tree[node*2]+tree[node];
        tree[node*2+1]=tree[node*2+1]+tree[node];
        tree[node]= {0, inf};
    }
    if(l<=s && e<=r) {
        tree[node]=tree[node]+diff;
    } else {
        update(node*2, s, (s+e)/2, l, r, diff);
        update(node*2+1, (s+e)/2+1, e, l, r, diff);
    }
}
wall query(int node, int s, int e, int num) {
    if(e<num || num<s) return{0, inf};
    if(s==e) return tree[node];
    return query(node*2, s, (s+e)/2, num)+query(node*2+1, (s+e)/2+1, e, num)+tree[node];
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    int h=(int)ceil(log2(n));
    int tree_size=1<<(h+1);
    tree.resize(tree_size);
    for(int i=0; i<k; ++i) {
        if(op[i]==1) { //+
            update(1, 1, n, left[i]+1, right[i]+1, {height[i], inf});
        } else { //-
            update(1, 1, n, left[i+1], right[i]+1, {0, height[i]});
        }
    }
    for(int i=0; i<n; ++i) {
        finalHeight[i]=query(1, 1, n, i+1).mx;
    }
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 175 ms 13944 KB Output is correct
3 Incorrect 235 ms 8060 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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