Submission #698149

#	Time	Username	Problem	Language	Result	Execution time	Memory
698149		Hacv16	Wall (IOI14_wall)	C++17	8 / 100	3084 ms	201760 KiB

wall

#include <bits/stdc++.h>
using namespace std;

#define fr first
#define sc second

typedef long long ll;
const int MAX = 2e6 + 15;
const int INF = 0x3f3f3f3f;

struct Node{
    ll mn, mx, lzset;

    Node(ll a = 0, ll b = 0, ll c = -1) : mn(a), mx(b), lzset(c) {}

    Node operator + (Node other){
        ll cmn = min(mn, other.mn);
        ll cmx = max(mx, other.mx);
        return Node(cmn, cmx);
    }
};

Node seg[4 * MAX];

void refresh(ll p, ll l, ll r){
    if(seg[p].lzset == -1) return;
    ll st = seg[p].lzset;

    seg[p].lzset = -1;
    seg[p].mn = st;
    seg[p].mx = st;

    if(l == r) return;

    ll e = 2 * p, d = e + 1;
    seg[e].lzset = st;
    seg[d].lzset = st;
}

void update(ll a, ll b, ll x, ll p, ll l, ll r, bool type){
    refresh(p, l, r);
    if(a > r || b < l) return;
    
    bool change = (type ? (seg[p].mx < x) : (seg[p].mn > x));
    if(l == r && !change) return;

    if(a <= l && r <= b && change){
        seg[p].lzset = x;
        refresh(p, l, r);
        return;
    }

    ll m = (l + r) >> 1, e = 2 * p, d = e + 1;
    update(a, b, x, e, l, m, type); update(a, b, x, d, m + 1, r, type);

    seg[p] = seg[e] + seg[d];
}

ll getVal(ll i, ll p, ll l, ll r){
    refresh(p, l, r);
    if(l == r) return seg[p].mn;
    ll m = (l + r) >> 1, e = 2 * p, d = e + 1;
    refresh(e, l, m); refresh(d, m + 1, r);
    if(i <= m) return getVal(i, e, l, m);
    return getVal(i, d, m + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 0; i < k; i++){
        ll l = left[i] + 1, r = right[i] + 1, h = height[i];
        if(op[i] == 1) update(l, r, h, 1, 1, n, 1);
        else update(l, r, h, 1, 1, n, 0);
    }

    for(int i = 0; i < n; i++)
        finalHeight[i] = getVal(i + 1, 1, 1, n);
}

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