Submission #1162669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162669		InvMOD	Wall (IOI14_wall)	C++20	100 / 100	568 ms	78700 KiB

wall

#include<bits/stdc++.h>

//#define name "InvMOD"
#ifndef name
    #include "wall.h"
#endif // name

using namespace std;

#define fi first
#define se second
#define dbg(x) "[" << #x " = " << (x) << "]"
#define pi pair<int,int>

struct SMT{
    int trsz;
    vector<pi> st;

    const pi base = {0, 1e9};

    SMT(int n = 0): trsz(n), st((n << 2 |1)) {
        for(int i = 0; i < (n << 2 | 1); i++){
            st[i] = base;
        }
    }

    void apply(int id, pi v){
        st[id].fi = max(st[id].fi, v.fi);
        st[id].fi = min(st[id].fi, v.se);
        st[id].se = min(st[id].se, v.se);
        st[id].se = max(st[id].se, v.fi);
    }

    void down(int id){
        apply(id << 1, st[id]);
        apply(id << 1|1, st[id]);
        st[id] = base;
    }

    void update(int id, int l, int r, int u, int v, pi h){
        if(l >= u && r <= v){
            apply(id, h);
        }
        else{
            int m = l+r>>1; down(id);
            if(u <= m) update(id << 1, l, m, u, v, h);
            if(v > m) update(id << 1|1, m+1, r, u, v, h);
        }
    }

    int query(int id, int l, int r, int x){
        if(l == r){
            return st[id].fi;
        }
        else{
            int m = l+r>>1; down(id);
            if(x <= m)
                return query(id << 1, l, m, x);
            else return query(id << 1|1, m+1, r, x);
        }
    }

    void upd(int l, int r, int op, int h){
        if(op&1){
            update(1, 0, trsz - 1, l, r, make_pair(h, 1e9));
        }
        else{
            update(1, 0, trsz - 1, l, r, make_pair(0, h));
        }
    }

    int get(int x){
        return query(1, 0, trsz - 1, x);
    }
};

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[]){
    SMT st(n);

    for(int i = 0; i < k; i++){
        st.upd(l[i], r[i], op[i], h[i]);
    }

    for(int i = 0; i < n; i++) fh[i] = st.get(i);
}

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