oj.uz

Submission #930129

# Submission time Handle Problem Language Result Execution time Memory
930129 2024-02-18T15:46:56 Z GrindMachine Wall (IOI14_wall) C++17
100 / 100
 1531 ms 65460 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/13442?#comment-184202

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "wall.h"

template<typename T>
struct lazysegtree {
    /*=======================================================*/

    struct data {
        int a;
    };

    struct lazy {
        int mn,mx;
    };

    data d_neutral = {0};
    lazy l_neutral = {inf1,-inf1};

    void merge(data &curr, data &left, data &right) {
        curr.a = left.a+right.a;
    }

    void create(int x, int lx, int rx, T v) {

    }

    void modify(int x, int lx, int rx, T v) {
        if(v.ff == 1){
            lz[x].mx = v.ss;
        }
        else{
            lz[x].mn = v.ss;
        }
    }

    void merge_lazy(lazy &l1, lazy &l2){
        // l2.mn < l1.mn => l1.mn decreases
        amin(l1.mn,l2.mn);
        // however, new min can't go below curr max
        amax(l1.mn,l2.mx);
        // new max can't go above curr min
        amin(l1.mx,l2.mn);
        // l2.mx > l1.mx => l1.mx increases
        amax(l1.mx,l2.mx);
    }

    void propagate(int x, int lx, int rx) {
        auto [mn,mx] = lz[x];
        amin(tr[x].a,mn);
        amax(tr[x].a,mx);

        if(rx-lx > 1){
            merge_lazy(lz[2*x+1],lz[x]);
            merge_lazy(lz[2*x+2],lz[x]);
        }

        lz[x] = l_neutral;
    }

    /*=======================================================*/

    int siz = 1;
    vector<data> tr;
    vector<lazy> lz;

    lazysegtree() {

    }

    lazysegtree(int n) {
        while (siz < n) siz *= 2;
        tr.assign(2 * siz, d_neutral);
        lz.assign(2 * siz, l_neutral);
    }

    void build(vector<T> &a, int n, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < n) {
                create(x, lx, rx, a[lx]);
            }

            return;
        }

        int mid = (lx + rx) / 2;

        build(a, n, 2 * x + 1, lx, mid);
        build(a, n, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void build(vector<T> &a, int n) {
        build(a, n, 0, 0, siz);
    }

    void rupd(int l, int r, T v, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return;
        if (lx >= l and rx <= r) {
            modify(x, lx, rx, v);
            propagate(x, lx, rx);
            return;
        }

        int mid = (lx + rx) / 2;

        rupd(l, r, v, 2 * x + 1, lx, mid);
        rupd(l, r, v, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void rupd(int l, int r, T v) {
        rupd(l, r + 1, v, 0, 0, siz);
    }

    data query(int l, int r, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return d_neutral;
        if (lx >= l and rx <= r) return tr[x];

        int mid = (lx + rx) / 2;

        data curr;
        data left = query(l, r, 2 * x + 1, lx, mid);
        data right = query(l, r, 2 * x + 2, mid, rx);

        merge(curr, left, right);
        return curr;
    }

    data query(int l, int r) {
        return query(l, r + 1, 0, 0, siz);
    }
};

void buildWall(int n, int m, int op[], int left[], int right[], int height[], int finalHeight[]){
    lazysegtree<pii> st(n);
    rep(i,m){
        int t = op[i], l = left[i], r = right[i], h = height[i];
        st.rupd(l,r,{t,h});
    }

    rep(i,n){
        finalHeight[i] = st.query(i,i).a;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 10 ms 860 KB Output is correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 7 ms 952 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 101 ms 8240 KB Output is correct
3 Correct 190 ms 4436 KB Output is correct
4 Correct 568 ms 11516 KB Output is correct
5 Correct 341 ms 11860 KB Output is correct
6 Correct 329 ms 11604 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 7 ms 856 KB Output is correct
6 Correct 8 ms 860 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 96 ms 8196 KB Output is correct
9 Correct 230 ms 4520 KB Output is correct
10 Correct 563 ms 11604 KB Output is correct
11 Correct 342 ms 11600 KB Output is correct
12 Correct 331 ms 11616 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 97 ms 8044 KB Output is correct
15 Correct 34 ms 1708 KB Output is correct
16 Correct 572 ms 11688 KB Output is correct
17 Correct 337 ms 12040 KB Output is correct
18 Correct 360 ms 11608 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 9 ms 1116 KB Output is correct
5 Correct 10 ms 860 KB Output is correct
6 Correct 7 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 96 ms 8020 KB Output is correct
9 Correct 191 ms 4432 KB Output is correct
10 Correct 590 ms 11608 KB Output is correct
11 Correct 335 ms 11604 KB Output is correct
12 Correct 336 ms 11604 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 99 ms 8240 KB Output is correct
15 Correct 35 ms 1712 KB Output is correct
16 Correct 612 ms 11588 KB Output is correct
17 Correct 340 ms 11860 KB Output is correct
18 Correct 333 ms 11608 KB Output is correct
19 Correct 1515 ms 65296 KB Output is correct
20 Correct 1531 ms 65460 KB Output is correct
21 Correct 1516 ms 65292 KB Output is correct
22 Correct 1512 ms 65320 KB Output is correct
23 Correct 1505 ms 65252 KB Output is correct
24 Correct 1522 ms 65336 KB Output is correct
25 Correct 1510 ms 65160 KB Output is correct
26 Correct 1511 ms 65140 KB Output is correct
27 Correct 1530 ms 65452 KB Output is correct
28 Correct 1511 ms 65212 KB Output is correct
29 Correct 1530 ms 65168 KB Output is correct
30 Correct 1510 ms 65204 KB Output is correct