oj.uz

Submission #1035037

# Submission time Handle Problem Language Result Execution time Memory
1035037 2024-07-26T03:22:10 Z TrinhKhanhDung Wall (IOI14_wall) C++14
100 / 100
 617 ms 96964 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

#include "wall.h"

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

struct SegmentTree{
    vector<int> up, down;
    int n;

    SegmentTree(int _n = 0){
        n = _n;
        up.resize(4 * n + 3, 0);
        down.resize(4 * n + 3);
        for(int i=1; i<=4*n; i++){
            down[i] = INF * 2;
        }
    }

    void push(int i){
        maximize(up[i * 2], up[i]);
        maximize(up[i * 2 + 1], up[i]);
        minimize(down[i * 2], down[i]);
        minimize(down[i * 2 + 1], down[i]);
        minimize(up[i * 2], down[i]);
        minimize(up[i * 2 + 1], down[i]);
        maximize(down[i * 2], up[i]);
        maximize(down[i * 2 + 1], up[i]);

        up[i] = 0;
        down[i] = INF * 2;
    }

    void update(int i, int l, int r, int u, int v, int h, int t){
        if(r < u || v < l) return;
        if(u <= l && r <= v){
            if(t == 1){
                maximize(up[i], h);
                maximize(down[i], h);
            }
            else{
                minimize(down[i], h);
                minimize(up[i], h);
            }
            return;
        }
        push(i);
        int m = (l + r) >> 1;
        update(i * 2, l, m, u, v, h, t);
        update(i * 2 + 1, m + 1, r, u, v, h, t);
    }

    void update(int u, int v, int h, int t){
        update(1, 0, n-1, u, v, h, t);
//        cout << u << ' ' << v << ' ' << h << ' ' << t << '\n';
    }

    int getVal(int p){
        int i = 1, l = 0, r = n-1;
        while(l < r){
            int m = (l + r) >> 1;
            push(i);
            if(p <= m){
                i = i * 2;
                r = m;
            }
            else{
                i = i * 2 + 1;
                l = m + 1;
            }
        }
        return up[i];
    }
};

const int MAX = 2e6 + 10;

int N, Q;
int t[MAX], L[MAX], R[MAX], H[MAX];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    N = n;
    Q = k;
    for(int i=0; i<Q; i++){
        t[i] = op[i];
        L[i] = left[i];
        R[i] = right[i];
        H[i] = height[i];
    }

    SegmentTree IT(n);
    for(int i=0; i<Q; i++){
        IT.update(L[i], R[i], H[i], t[i]);
    }
    for(int i=0; i<N; i++){
        finalHeight[i] = IT.getVal(i);
    }
}

//signed main(){
//    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("task.inp", "r", stdin);
//    freopen("task.out", "w", stdout);

//    cin >> N >> Q;
//    SegmentTree IT(N);
//    for(int i=1; i<=Q; i++){
////        int l, r, h, t;
//        cin >> t >> l >> r >> h;
//        IT.update(l, r, h, t);
//        for(int j=0; j<N; j++){
//            cout << IT.getVal(j) << ' ';
//        }
//        cout << '\n';
//    }

//    for(int i=0; i<N; i++){
//        cout << IT.getVal(i) << '\n';
//    }
//
//    return 0;
//}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 860 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 85 ms 21840 KB Output is correct
3 Correct 126 ms 11140 KB Output is correct
4 Correct 387 ms 29152 KB Output is correct
5 Correct 175 ms 29608 KB Output is correct
6 Correct 170 ms 28244 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 508 KB Output is correct
4 Correct 5 ms 1088 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 83 ms 21840 KB Output is correct
9 Correct 134 ms 11348 KB Output is correct
10 Correct 399 ms 29268 KB Output is correct
11 Correct 192 ms 29776 KB Output is correct
12 Correct 183 ms 28152 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 88 ms 21760 KB Output is correct
15 Correct 25 ms 2592 KB Output is correct
16 Correct 440 ms 29116 KB Output is correct
17 Correct 185 ms 28496 KB Output is correct
18 Correct 187 ms 28496 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 1 ms 672 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1084 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 88 ms 21760 KB Output is correct
9 Correct 146 ms 11196 KB Output is correct
10 Correct 385 ms 29264 KB Output is correct
11 Correct 183 ms 29776 KB Output is correct
12 Correct 175 ms 28240 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 86 ms 21944 KB Output is correct
15 Correct 26 ms 2396 KB Output is correct
16 Correct 420 ms 29224 KB Output is correct
17 Correct 188 ms 28456 KB Output is correct
18 Correct 195 ms 28624 KB Output is correct
19 Correct 585 ms 96852 KB Output is correct
20 Correct 578 ms 96848 KB Output is correct
21 Correct 576 ms 96964 KB Output is correct
22 Correct 564 ms 96852 KB Output is correct
23 Correct 559 ms 96852 KB Output is correct
24 Correct 566 ms 96780 KB Output is correct
25 Correct 576 ms 96848 KB Output is correct
26 Correct 578 ms 96852 KB Output is correct
27 Correct 617 ms 96800 KB Output is correct
28 Correct 564 ms 96852 KB Output is correct
29 Correct 596 ms 96940 KB Output is correct
30 Correct 576 ms 96840 KB Output is correct