oj.uz

Submission #933705

# Submission time Handle Problem Language Result Execution time Memory
933705 2024-02-26T06:52:39 Z Regulus Wall (IOI14_wall) C++17
100 / 100
 672 ms 90276 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 9 ms 4812 KB Output is correct
5 Correct 4 ms 4808 KB Output is correct
6 Correct 4 ms 4904 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 120 ms 12316 KB Output is correct
3 Correct 158 ms 8144 KB Output is correct
4 Correct 491 ms 13904 KB Output is correct
5 Correct 225 ms 14432 KB Output is correct
6 Correct 235 ms 14480 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 7 ms 4700 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 4 ms 4696 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 108 ms 18004 KB Output is correct
9 Correct 155 ms 11828 KB Output is correct
10 Correct 443 ms 23520 KB Output is correct
11 Correct 210 ms 24404 KB Output is correct
12 Correct 201 ms 23020 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 115 ms 18040 KB Output is correct
15 Correct 33 ms 5868 KB Output is correct
16 Correct 566 ms 23888 KB Output is correct
17 Correct 215 ms 23120 KB Output is correct
18 Correct 215 ms 23124 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4616 KB Output is correct
3 Correct 3 ms 4440 KB Output is correct
4 Correct 8 ms 4700 KB Output is correct
5 Correct 7 ms 4752 KB Output is correct
6 Correct 7 ms 4700 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 111 ms 17944 KB Output is correct
9 Correct 165 ms 12040 KB Output is correct
10 Correct 449 ms 23520 KB Output is correct
11 Correct 226 ms 24552 KB Output is correct
12 Correct 209 ms 23004 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 124 ms 18080 KB Output is correct
15 Correct 35 ms 5864 KB Output is correct
16 Correct 641 ms 23780 KB Output is correct
17 Correct 218 ms 23120 KB Output is correct
18 Correct 219 ms 23120 KB Output is correct
19 Correct 628 ms 89988 KB Output is correct
20 Correct 607 ms 87708 KB Output is correct
21 Correct 611 ms 90244 KB Output is correct
22 Correct 605 ms 87876 KB Output is correct
23 Correct 604 ms 87680 KB Output is correct
24 Correct 604 ms 87640 KB Output is correct
25 Correct 604 ms 87800 KB Output is correct
26 Correct 672 ms 90276 KB Output is correct
27 Correct 612 ms 90128 KB Output is correct
28 Correct 612 ms 87540 KB Output is correct
29 Correct 602 ms 87624 KB Output is correct
30 Correct 601 ms 87456 KB Output is correct