oj.uz

Submission #933698

# Submission time Handle Problem Language Result Execution time Memory
933698 2024-02-26T06:45:08 Z Regulus Wall (IOI14_wall) C++17
0 / 100
 1 ms 4444 KB 
#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 ans[N], laz[N<<2], laz2[N<<2], Seg[N<<2];
#ifdef TEST
int op[N], L[N], R[N], h[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] = 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -