oj.uz

Submission #637483

# Submission time Handle Problem Language Result Execution time Memory
637483 2022-09-02T06:48:33 Z Ez0zIOVgTsSgT Wall (IOI14_wall) C++14
100 / 100
 757 ms 169772 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;

struct Dat {
    int mn, mx;
};

struct SegTree {
    int N;
    V<Dat> seg, lazy;
    vi ans;
    void init(int _N) {
        N = _N;
        seg.assign(N*4 + 7, {0,0});
        lazy.assign(N*4 + 7, {0,0});
        ans.assign(N+5, 0);
    }
    void proc_add(int ind, int val) {
        ckmax(seg[ind].mn, val);
        ckmax(seg[ind].mx, val);
        ckmax(lazy[ind].mn, val);
        ckmax(lazy[ind].mx, val);
    }
    void proc_rem(int ind, int val) {
        ckmin(seg[ind].mn, val);
        ckmin(seg[ind].mx, val);
        ckmin(lazy[ind].mn, val);
        ckmin(lazy[ind].mx, val);
    }
    void push(int ind) {
        if(lazy[ind].mx != -MOD) {
            F0R(i, 2) proc_add(ind*2 + i, lazy[ind].mx);
        }
        if(lazy[ind].mn != MOD) {
            F0R(i, 2) proc_rem(ind*2 + i, lazy[ind].mn);
        }
        lazy[ind] = {MOD, -MOD};
    }
    void pull(int ind) {
        seg[ind].mn = min(seg[ind<<1].mn, seg[ind<<1|1].mn);
        seg[ind].mx = max(seg[ind<<1].mx, seg[ind<<1|1].mx);
    }
    void upd(int op, int l, int r, int val, int ind, int L, int R) {
        if(L > r || R < l) return;
        if(l <= L && R <= r) {
            if(op == 1) proc_add(ind, val);
            else proc_rem(ind, val);
            return;
        }
        push(ind);
        int mid = (L + R) >> 1;
        upd(op, l, r, val, ind<<1, L, mid);
        upd(op, l, r, val, ind<<1|1, mid+1, R);
        pull(ind);
    }
    void upd(int op, int l, int r, int val) {
        upd(op, l, r, val, 1, 1, N);
    }
    void calc(int ind, int L, int R) {
        if(L == R) ans[L] = seg[ind].mn;
        else {
            push(ind);
            int mid = (L + R) >> 1;
            calc(ind<<1, L, mid);
            calc(ind<<1|1, mid+1, R);
        }
    }
    void calc() {
        calc(1, 1, N);
    }
};

SegTree st;

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
    st.init(N);
    F0R(i, K) {
        st.upd(op[i], left[i]+1, right[i]+1, height[i]);
    }
    st.calc();
    FOR(i,1,N+1) finalHeight[i-1] = st.ans[i];
}

Compilation message

wall.cpp: In function 'void setIO(std::string)':
wall.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1236 KB Output is correct
5 Correct 5 ms 1204 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 128 ms 13876 KB Output is correct
3 Correct 205 ms 6684 KB Output is correct
4 Correct 627 ms 17196 KB Output is correct
5 Correct 283 ms 17912 KB Output is correct
6 Correct 283 ms 17836 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 1140 KB Output is correct
5 Correct 5 ms 1236 KB Output is correct
6 Correct 5 ms 1208 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 129 ms 9972 KB Output is correct
9 Correct 204 ms 6728 KB Output is correct
10 Correct 576 ms 17224 KB Output is correct
11 Correct 284 ms 17840 KB Output is correct
12 Correct 286 ms 17780 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 128 ms 9996 KB Output is correct
15 Correct 41 ms 2640 KB Output is correct
16 Correct 757 ms 17588 KB Output is correct
17 Correct 292 ms 17628 KB Output is correct
18 Correct 297 ms 17648 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 8 ms 1188 KB Output is correct
5 Correct 5 ms 1236 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 131 ms 9900 KB Output is correct
9 Correct 215 ms 6720 KB Output is correct
10 Correct 569 ms 17204 KB Output is correct
11 Correct 296 ms 17896 KB Output is correct
12 Correct 281 ms 17756 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 132 ms 10180 KB Output is correct
15 Correct 46 ms 2632 KB Output is correct
16 Correct 755 ms 17612 KB Output is correct
17 Correct 291 ms 17676 KB Output is correct
18 Correct 303 ms 17608 KB Output is correct
19 Correct 703 ms 161268 KB Output is correct
20 Correct 706 ms 167204 KB Output is correct
21 Correct 694 ms 169736 KB Output is correct
22 Correct 690 ms 167340 KB Output is correct
23 Correct 702 ms 167264 KB Output is correct
24 Correct 692 ms 167148 KB Output is correct
25 Correct 694 ms 167132 KB Output is correct
26 Correct 689 ms 169772 KB Output is correct
27 Correct 700 ms 169700 KB Output is correct
28 Correct 690 ms 167244 KB Output is correct
29 Correct 701 ms 167164 KB Output is correct
30 Correct 686 ms 167328 KB Output is correct