Submission #291136

#	Time	Username	Problem	Language	Result	Execution time	Memory
291136		ivan24	Wall (IOI14_wall)	C++14	100 / 100	1452 ms	132672 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

const ll INF = 1e9;

class SegmentTree {
private:
    vi st, data;
    vii lzy;
    ll n;
    ll left(ll x){ return (x << 1); }
    ll right(ll x) { return ((x << 1) + 1); }
    ii cmbNodes(ii lhs, ii rhs){
        ii ans = ii(max(lhs.F,rhs.F),min(lhs.S,rhs.S));
        if (ans.F <= ans.S) return ans;
        if (lhs.S < rhs.F) ans.F = lhs.S;
        else ans.S = lhs.F;
        return ans;
    }
    void rangeUpdate (ll i, ll l, ll r, ll ul, ll ur, ii newNode){
        //cout << i << " " << l << " " << r << " " << ul << " " << ur << " " << endl;
        if (l != r){
            lzy[left(i)] = cmbNodes(lzy[i],lzy[left(i)]);
            lzy[right(i)] = cmbNodes(lzy[i],lzy[right(i)]);
            lzy[i] = ii(0,INF);
        }
        if (ur >= r && l >= ul){
            lzy[i] = cmbNodes(newNode,lzy[i]);
        }else if (max(ul,l) <= min(ur,r)){
            ll m = (l+r)/2;
            rangeUpdate(left(i),l,m,ul,ur,newNode);
            rangeUpdate(right(i),m+1,r,ul,ur,newNode);
        }
    }
    ii query (ll i, ll l, ll r, ll idx){
        if (r >= idx && idx >= l){
            ii ans = lzy[i];
            ll m = (l+r)/2;
            if (l != r){
                ii lans = query(left(i),l,m,idx);
                ii rans = query(right(i),m+1,r,idx);
                ans = cmbNodes(ans,lans);
                ans = cmbNodes(ans,rans);
            }
            return ans;
        }else{
            return ii(0,INF);
        }
    }
    void printLzy(ll i, ll l, ll r){
        cout << i << "  " << l << "-" << r << " : " << lzy[i].F << " , " << lzy[i].S << endl;
        if (l != r){
            ll m = (l+r)/2;
            printLzy(left(i),l,m);
            printLzy(right(i),m+1,r);
        }
    }
    void build (ll i, ll l, ll r){
        if (l == r){
            lzy[i] = ii(0,0);
        }else{
            lzy[i] = ii(0,INF);
            ll m = (l+r)/2;
            build(left(i),l,m);
            build(right(i),m+1,r);
        }
    }
public:
    SegmentTree (ll sz): st(sz*4), data(sz), lzy(sz*4,ii(0,0)), n(sz){
        build(1,0,n-1);
    }
    void update (ll l, ll r, ii newNode){
        rangeUpdate(1,0,n-1,l,r,newNode);
    }
    ll query (ll idx){
        ii ans = query(1,0,n-1,idx);
        //cout << ans.F << " " << ans.S << endl;
        return ans.F;
    }
    vi get_all_data(){
        vi ans(n);
        for (ll i = 0; n > i; i++) ans[i] = query(i);
        return ans;
    }
    void print(){
        printLzy(1,0,n-1);
    }
    void print_data(){
        vi res = get_all_data();
        for (auto i: res) cout << i << " ";
        cout << endl;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SegmentTree st(n);
    for (ll i = 0; k > i; i++){
        //cout << i << endl;
        ii newNode = ii(0,INF);
        if (op[i] == 1) newNode.F = height[i];
        else newNode.S = height[i];
        st.update(left[i],right[i],newNode);
        //st.print_data();
        //st.print();
    }
    //st.print();
    vi res = st.get_all_data();
    for (ll i = 0; n > i; i++) finalHeight[i] = abs(res[i]);
}

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