Submission #698147

#	Time	Username	Problem	Language	Result	Execution time	Memory
698147		Hacv16	Wall (IOI14_wall)	C++17	0 / 100	3049 ms	107820 KiB

wall

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define fr first
#define sc second

typedef long long ll;
const int MAX = 1e6 + 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 mn = min(mn, other.mn);
        ll mx = max(mx, other.mx);
        return Node(mn, mx);
    }
};

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;
    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++){
        int 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);
}

Compilation message (stderr)

wall.cpp: In function 'void _Z6updatexxxxxxb.part.0(ll, ll, ll, ll, ll, ll, bool)':
wall.cpp:20:12: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |         ll mn = min(mn, other.mn);
      |            ^~
wall.cpp:21:12: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |         ll mx = max(mx, other.mx);
      |            ^~
wall.cpp: In function 'void update(ll, ll, ll, ll, ll, ll, bool)':
wall.cpp:20:12: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |         ll mn = min(mn, other.mn);
      |            ^~
wall.cpp:21:12: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |         ll mx = max(mx, other.mx);
      |            ^~

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