Submission #1156446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156446		Esgeer	Wall (IOI14_wall)	C++17	61 / 100	534 ms	12844 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2")
#endif
//#define int long long
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vb vector<bool>
#define vvb vector<vb>
#define endl '\n'
#define sp <<' '<<
#define F(i, s, n) for(int i = s; i < (int) n; i++)
#define pb push_back
#define fi first
#define se second

const int N = 1e5+5;
const int inf = 1e7;

struct Update {
    int mn, mx;
};
Update lazy[N*4];
int a[N];

Update merge(Update nw, Update old) {
    Update merged;
    merged.mn = max(old.mn, nw.mn);
    merged.mx = min(old.mx, nw.mx);
    if(merged.mn > merged.mx) {
        if(nw.mn > old.mx) {
            merged.mx = merged.mn;
        } else {
            merged.mn = merged.mx;
        }
    }
    return merged;
}

void push_down(int node, int l, int r) {
    if(lazy[node].mn == 0 && lazy[node].mx == inf) return;
    if(l == r) {
        //cout << "I am here" sp l sp lazy[node].mn << endl;
        a[l] = lazy[node].mn;
        return; 
    }
    lazy[node*2+1] = merge(lazy[node], lazy[node*2+1]);
    lazy[node*2+2] = merge(lazy[node], lazy[node*2+2]);
    lazy[node] = {0, inf};
}

void update(int node, int l, int r, int L, int R, int mn, int mx) {
    push_down(node, l, r);
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        //cout << "UPD" sp l sp r sp mn sp mx <<endl;
        lazy[node] = merge({mn, mx}, lazy[node]);
        return;
    }
    int m = (l + r) >> 1;

    update(node*2+1, l, m, L, R, mn, mx);
    update(node*2+2, m+1, r, L, R, mn, mx);
}

void finalize(int node, int l, int r) {
    push_down(node, l, r);
    if(l != r) {
        int m = (l + r) >> 1;
        finalize(node*2+1, l, m);
        finalize(node*2+2, m+1, r);
    }
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    F(i, 0, n*4) lazy[i] = {0, inf};
    F(i, 0, k) {
        if(op[i] == 1) {
            update(0, 0, n-1, left[i], right[i], height[i], inf);
        } else {
            update(0, 0, n-1, left[i], right[i], 0, height[i]);
        }
    }
    finalize(0, 0, n-1);
    F(i, 0, n) finalHeight[i] = a[i];
    return;
}

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