oj.uz

Submission #1092848

# Submission time Handle Problem Language Result Execution time Memory
1092848 2024-09-25T08:51:07 Z daviedu Wall (IOI14_wall) C++17
8 / 100
 3000 ms 13960 KB 
#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int) (a).size()
#define ll long long
#define ld long double
#define pb push_back

struct P{
    ll x, y;
};

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

#define bound array<int, 2>

const bound neutral = {0, INT_MAX};
const bound no_lazy = {-1, -1};
const int MI = 0, MA = INT_MAX;

class Segtree{
public:
    int n;
    vector<int> t, hi, lo; // lazy is not a bound, but an operation with 2 parameters
    Segtree(int size){
        n = 1;
        while (n < size) n <<= 1;
        t.resize(2*n);
        hi.resize(2*n, MI);
        lo.resize(2*n, MA);
    }
    void apply(int i){
        t[i] = max(t[i], hi[i]);
        t[i] = min(t[i], lo[i]);
        hi[i] = MI;
        lo[i] = MA;
    }
    void prop(int i){
        if (lo[i] == MA && hi[i] == MI) return;
        if (i >= n) apply(i);
        else{
            prop(2*i);
            prop(2*i+1);
            lo[2*i] = lo[2*i+1] = lo[i];
            hi[2*i] = hi[2*i+1] = hi[i];
            hi[i] = MI;
            lo[i] = MA;
        }
    }
    void update(int l, int r, int i, int a, int b, int v, int op){
        prop(i);
        if (b < l || r < a) return;
        if (a <= l && r <= b){
            if (op == 1) hi[i] = v;
            else lo[i] = v;
            return;
        }
        int m = (l+r)/2;
        update(l, m, 2*i, a, b, v, op);
        update(m+1, r, 2*i+1, a, b, v, op);
    }
    void update(int l, int r, int v, int op){
        update(0, n-1, 1, l, r, v, op);
    }

    int query(int l, int r, int i, int pos){
        prop(i);
        if (l == r && l == pos) return t[i];
        int m = (l+r)/2;
        if (pos <= m) return query(l, m, 2*i, pos);
        else return query(m+1, r, 2*i+1, pos);
    }
    int query(int pos){
        return query(0, n-1, 1, pos);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    Segtree seg (n);
    for (int i=0; i<k; i++){
        seg.update(left[i], right[i], height[i], op[i]);
    }
    for (int i=0; i<n; i++){
        finalHeight[i] = seg.query(i);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 102 ms 860 KB Output is correct
5 Correct 88 ms 856 KB Output is correct
6 Correct 83 ms 1020 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 82 ms 13960 KB Output is correct
3 Execution timed out 3063 ms 8212 KB Time limit exceeded
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 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 101 ms 1024 KB Output is correct
5 Correct 83 ms 1020 KB Output is correct
6 Correct 91 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 81 ms 13920 KB Output is correct
9 Execution timed out 3051 ms 8272 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 107 ms 860 KB Output is correct
5 Correct 83 ms 1016 KB Output is correct
6 Correct 88 ms 1028 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 86 ms 13868 KB Output is correct
9 Execution timed out 3093 ms 8068 KB Time limit exceeded
10 Halted 0 ms 0 KB -