Submission #933705

#	Time	Username	Problem	Language	Result	Execution time	Memory
933705		Regulus	Wall (IOI14_wall)	C++17	100 / 100	672 ms	90276 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define bug(x) cerr << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
//#define TEST
const int N = 2e6+5;
const int INF = 2e9;
int laz[N<<2], laz2[N<<2], Seg[N<<2];
#ifdef TEST
int op[N], L[N], R[N], h[N], ans[N];
#endif

inline void build(int L, int R, int v)
{
    laz[v] = laz2[v] = -1;
    if (L == R) return;
    int mid((L+R) >> 1);
    build(L, mid, v<<1), build(mid+1, R, v<<1|1);
}

inline void mod1(int v, pll p)
{
    if (Seg[v] != -1) Seg[v] = max(Seg[v], (int)p.S);
    laz[v] = (laz[v] == -1)?p.S : max(laz[v], (int)p.S);
    if (laz2[v] != -1 && laz[v] > laz2[v]) laz2[v] = laz[v];
}

inline void mod2(int v, pll p)
{
    if (Seg[v] != -1) Seg[v] = min(Seg[v], (int)p.S);
    laz2[v] = (laz2[v] == -1)?p.S : min(laz2[v], (int)p.S);
    if (laz[v] != -1 && laz2[v] < laz[v]) laz[v] = laz2[v];
}

inline void push(int L, int R, int v)
{
    if (laz[v] != -1)
    {
        mod1(v<<1, {1, laz[v]}), mod1(v<<1|1, {1, laz[v]});
    }
    if (laz2[v] != -1)
    {
        mod2(v<<1, {2, laz2[v]}), mod2(v<<1|1, {2, laz2[v]});
    }

    laz[v] = laz2[v] = -1;
}

inline void pull(int v)
{
    if (Seg[v<<1] == Seg[v<<1|1] && Seg[v<<1] != -1)
        Seg[v] = Seg[v<<1];
    else Seg[v] = -1;
}

inline void modify(int L, int R, int ql, int qr, int v, pll p)
{
    if (ql <= L && R <= qr)
    {
        if (p.F == 1) mod1(v, p);
        else mod2(v, p);
        return;
    }

    int mid((L+R) >> 1);
    push(L, R, v);
    if (ql <= mid) modify(L, mid, ql, qr, v<<1, p);
    if (qr > mid) modify(mid+1, R, ql, qr, v<<1|1, p);
    pull(v);
}

inline int query(int L, int R, int pos, int v)
{
    if (L == R) return Seg[v];
    int mid((L+R) >> 1);
    push(L, R, v);
    if (pos <= mid) return query(L, mid, pos, v<<1);
    return query(mid+1, R, pos, v<<1|1);
}

void buildWall(int n, int Q, int op[], int L[], int R[], int h[], int ans[])
{
    build(1, n, 1);
    for (int i=0; i < Q; ++i)
    {
        ++L[i], ++R[i];
        modify(1, n, L[i], R[i], 1, {op[i], h[i]});
    }

    for (int i=1; i <= n; ++i)
    {
        ans[i-1] = query(1, n, i, 1);
    }
}

#ifdef TEST
int main(void)
{ IO
    int n, i, Q;

    cin >> n >> Q;
    for (i=0; i < Q; ++i)
        cin >> op[i] >> L[i] >> R[i] >> h[i];
    
    buildWall(n, Q, op, L, R, h, ans);
    for (i=1; i <= n; ++i) cout << ans[i] << '\n';

    return 0;
}
#endif

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