Submission #1209852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209852		jonteo_2001	Wall (IOI14_wall)	C++20	8 / 100	3071 ms	279472 KiB

wall

#pragma once
#include <bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
#define ll long long
#define debug(x) std::cerr << #x << " = " << (x) << std::endl

using namespace std;
struct ops {
    int type, val;
    ops(int type, int val): type(type), val(val){}
};
class SegTree {
public:
    vector<int> t; 
    vector<deque<ops>> lazy;

    SegTree(int n){
        t = vector<int> (4*n);
        lazy = vector<deque<ops>>(4*n, deque<ops>());
    }

    void apply(int v, int tl, int tr, deque<ops> above_ops){
        while (!above_ops.empty()){
            ops op = above_ops.front(); above_ops.pop_front();
            // cerr << "op = " << op.type << ", " << op.val << endl;
            // combine with any below ops as far as possible
            while (!lazy[v].empty()){
                ops last = lazy[v].back();
                // cerr << "last.type = " << last.type<<endl;
                if (last.type == 0 || op.type == 0){
                    if (last.type == 0){
                        switch (op.type){
                            case 1: op.val = max(op.val, last.val); break;
                            case 2: op.val = min(op.val, last.val); break;
                            default: break;
                        }
                    }
                    // lazy[v].clear();
                    op.type = 0;
                    break;
                }
                // Case 1: types are the same
                if (last.type == op.type){
                    if (last.type == 1){
                        op.val = max(op.val,last.val);
                    } else if (last.type == 2){
                        op.val = min(op.val,last.val);
                    } else assert(false);
                    lazy[v].pop_back();
                } else {
                    // one min, one max and if the values are the same, just break.
                    if (last.val == op.val){
                        // lazy[v].clear();
                        op.type = 0;
                        break;
                    }
                    if (last.type == 1 && op.type == 2){
                        // last = max, op = min
                        if (op.val < last.val){
                            // lazy[v].pop_back();
                            op.type = 0;
                            break;
                        } else {
                            // cannot combine
                            break;
                        }
                    } else {
                        // last = min, op = max
                        if (op.val > last.val){
                            op.type = 0;
                            break;
                            // lazy[v].pop_back();
                        } else{
                            // cannot combine
                            break;
                        }
                    }
                }
            }
            if (op.type == 0){
                lazy[v].clear();
            }
            lazy[v].push_back(op);
        }
        // cerr << "***********" << endl;
    }

    void prop(int v, int tl, int tr){
        if (tl == tr) {
            while (!lazy[v].empty()){
                ops cur_op = lazy[v].front();
                lazy[v].pop_front();
                switch (cur_op.type){
                    case 0: t[v] = cur_op.val; break;
                    case 1: t[v] = max(t[v], cur_op.val); break;
                    case 2: t[v] = min(t[v], cur_op.val); break;
                    default: assert(false);
                }
            }
            return;
        }
        int tm = (tl + tr) / 2;
        apply(v*2, tl, tm, lazy[v]);
        apply(v*2+1, tm+1, tr, lazy[v]);
        lazy[v].clear();
    }
    
    void update(int v, int tl, int tr, int l, int r, ops op){
        if (r < tl || tr < l) return;
        if (l <= tl && tr <= r){
            deque<ops> cur_ops; cur_ops.push_back(op);
            apply(v, tl, tr, cur_ops);
        } else{
            prop(v, tl, tr);
            int tm = (tl + tr) / 2;
            update(v*2, tl, tm, l, r, op);
            update(v*2+1, tm+1, tr, l, r, op);
        }
    }

    void query(int v, int tl, int tr, int* a){
        prop(v, tl, tr);
        if (tl == tr){
            a[tl] = t[v];
            return;
        }
        int tm = (tl + tr) / 2;
        query(v*2, tl, tm, a);
        query(v*2+1, tm+1, tr, a);
    }
};
// Write implementation prototypes Here
void buildWall(int n, int k, int* op, int* left, int* right, int* height, int* finalHeight){
    // PRINT THE ANSWER!
    // finalHeight.resize(n);
    SegTree st = SegTree(n);
    for (int i = 0; i < k; ++i){
        ops cur = ops(op[i], height[i]);
        st.update(1, 0, n-1, left[i], right[i], cur);
        // st.query(1, 0, n-1, finalHeight);
    }
    st.query(1, 0, n-1, finalHeight);
}
// Driver code
// int main(){
//     ios::sync_with_stdio(0);
//     cin.tie(0), cout.tie(0);
//     if (fopen("test.inp", "r") != NULL) {
//         freopen("test.inp", "r", stdin);
//         freopen("test.out", "w", stdout);
//         freopen("test.err", "w", stderr);
//     }
//     int n, k; cin >> n >> k;
//     vector<int> op(k), left(k), right(k), height(k);
//     for (int i = 0; i < k; ++i){
//         cin >> op[i] >> left[i] >> right[i] >> height[i];
//     }
//     vector<int> finalHeight(n);

//     buildWall(n, k, op, left, right, height, finalHeight);
//     for (auto it: finalHeight){
//         cout << it << " ";
//     }
//     cout << endl;
//     return 0;
// }

Compilation message (stderr)

wall.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39