Submission #289335

#	Time	Username	Problem	Language	Result	Execution time	Memory
289335		BeanZ	Wall (IOI14_wall)	C++14	100 / 100	1048 ms	100128 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

#define ll int
#define endl '\n'
const int N = 2e6 + 5;
ll stmin[N * 4], stmax[N * 4];
ll lazymin[N * 4], lazymax[N * 4];
ll res[N];
void down(ll k){
        stmax[k << 1] = max(stmax[k << 1], lazymax[k]);
        stmax[k << 1] = min(stmax[k << 1], lazymin[k]);
        stmin[k << 1] = min(stmin[k << 1], lazymin[k]);
        stmin[k << 1] = max(stmin[k << 1], lazymax[k]);

        stmax[k << 1 | 1] = max(stmax[k << 1 | 1], lazymax[k]);
        stmax[k << 1 | 1] = min(stmax[k << 1 | 1], lazymin[k]);
        stmin[k << 1 | 1] = min(stmin[k << 1 | 1], lazymin[k]);
        stmin[k << 1 | 1] = max(stmin[k << 1 | 1], lazymax[k]);

        lazymax[k << 1 | 1] = max(lazymax[k << 1 | 1], lazymax[k]);
        lazymin[k << 1 | 1] = min(lazymin[k << 1 | 1], lazymin[k]);
        lazymin[k << 1 | 1] = max(lazymin[k << 1 | 1], lazymax[k]);
        lazymax[k << 1 | 1] = min(lazymax[k << 1 | 1], lazymin[k]);

        lazymax[k << 1] = max(lazymax[k << 1], lazymax[k]);
        lazymin[k << 1] = min(lazymin[k << 1], lazymin[k]);
        lazymin[k << 1] = max(lazymin[k << 1], lazymax[k]);
        lazymax[k << 1] = min(lazymax[k << 1], lazymin[k]);

        lazymax[k] = -1e9;
        lazymin[k] = 1e9;
}
void upd(ll type, ll k, ll l, ll r, ll x, ll y, ll h){
        if (x > r || y < l) return;
        if (l != r) down(k);
        if (x <= l && y >= r){
                if (type == 1){
                        stmin[k] = max(stmin[k], h);
                        lazymin[k] = max(lazymin[k], h);
                        lazymax[k] = max(lazymax[k], h);
                        stmax[k] = max(stmax[k], h);
                } else {
                        stmax[k] = min(stmax[k], h);
                        stmin[k] = min(stmin[k], h);
                        lazymax[k] = min(lazymax[k], h);
                        lazymin[k] = min(lazymin[k], h);
                }
                return;
        }
        ll mid = (l + r) >> 1;
        upd(type, k << 1, l, mid, x, y, h);
        upd(type, k << 1 | 1, mid + 1, r, x, y, h);
}
void get(ll k, ll l, ll r){
        if (l != r) down(k);
        if (l == r){
                res[l] = stmax[k];
                return;
        }
        ll mid = (l + r) >> 1;
        get(k << 1, l, mid);
        get(k << 1 | 1, mid + 1, r);
}
void build(ll k, ll l, ll r){
        lazymin[k] = 1e9;
        lazymax[k] = -1e9;
        if (l == r) return;
        ll mid = (l + r) >> 1;
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
}
void buildWall(ll n, ll k, ll op[], ll left[], ll right[], ll height[], ll finalHeight[]){
        build(1, 1, n);
        for (int i = 1; i <= k; i++){
                upd(op[i - 1], 1, 1, n, left[i - 1] + 1, right[i - 1] + 1, height[i - 1]);
        }
        get(1, 1, n);
        for (int i = 1; i <= n; i++) finalHeight[i - 1] = res[i];
}
/*
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("time.in", "r")){
                freopen("time.in", "r", stdin);
                freopen("time.out", "w", stdout);
        }
        int tc, n; cin >> n >> tc;
        build(1, 1, n);
        while(tc--){
                int le, ri, op, h;
                cin >> op >> le >> ri >> h;
                upd(op, 1, 1, n, le + 1, ri + 1, h);
        }
        comp(1, 1, n);
        for(int i = 1; i <= n; ++i)
                cout << res[i] << ' ';
}
/*
*/

Compilation message (stderr)

wall.cpp:102:1: warning: "/*" within comment [-Wcomment]
  102 | /*
      |

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39