oj.uz

Submission #930127

# Submission time Handle Problem Language Result Execution time Memory
930127 2024-02-18T15:39:28 Z GrindMachine Wall (IOI14_wall) C++17
100 / 100
 1535 ms 65488 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){
        amin(l1.mn,l2.mn);
        amax(l1.mn,l2.mx);
        amin(l1.mx,l2.mn);
        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 1 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 8 ms 856 KB Output is correct
5 Correct 7 ms 956 KB Output is correct
6 Correct 7 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 96 ms 8148 KB Output is correct
3 Correct 194 ms 4380 KB Output is correct
4 Correct 572 ms 11544 KB Output is correct
5 Correct 335 ms 11612 KB Output is correct
6 Correct 342 ms 11616 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 2 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 7 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 98 ms 8144 KB Output is correct
9 Correct 197 ms 4516 KB Output is correct
10 Correct 567 ms 12120 KB Output is correct
11 Correct 360 ms 11604 KB Output is correct
12 Correct 330 ms 11600 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 101 ms 8016 KB Output is correct
15 Correct 35 ms 1560 KB Output is correct
16 Correct 564 ms 11604 KB Output is correct
17 Correct 333 ms 11600 KB Output is correct
18 Correct 341 ms 11604 KB Output is correct

Subtask #4
39.0 / 39.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 812 KB Output is correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 7 ms 948 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 96 ms 8148 KB Output is correct
9 Correct 196 ms 4692 KB Output is correct
10 Correct 562 ms 11604 KB Output is correct
11 Correct 337 ms 11652 KB Output is correct
12 Correct 335 ms 11588 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 105 ms 8044 KB Output is correct
15 Correct 34 ms 1712 KB Output is correct
16 Correct 566 ms 11556 KB Output is correct
17 Correct 337 ms 11600 KB Output is correct
18 Correct 355 ms 11604 KB Output is correct
19 Correct 1535 ms 65488 KB Output is correct
20 Correct 1510 ms 65248 KB Output is correct
21 Correct 1516 ms 65104 KB Output is correct
22 Correct 1503 ms 65148 KB Output is correct
23 Correct 1517 ms 65180 KB Output is correct
24 Correct 1517 ms 65468 KB Output is correct
25 Correct 1529 ms 65256 KB Output is correct
26 Correct 1530 ms 65184 KB Output is correct
27 Correct 1506 ms 65276 KB Output is correct
28 Correct 1508 ms 65456 KB Output is correct
29 Correct 1515 ms 65200 KB Output is correct
30 Correct 1529 ms 65200 KB Output is correct