Submission #1196367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196367		AMel0n	Wall (IOI14_wall)	C++20	0 / 100	108 ms	8008 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FOR(i,N) for(int i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first 
#define S second

const int INF = 1e9+7;

int N;
vector<int> tree;
vector<pair<int,int>> lazy;

void pushdown(int tl, int tr, int i) {
    if (lazy[i].F != -INF) {
        if (tree[i] < lazy[i].F && lazy[i].S == 1) tree[i] = lazy[i].F; // add
        if (tree[i] > lazy[i].F && lazy[i].S == 2) tree[i] = lazy[i].F; // remove
        if (tl != tr) {
            lazy[i*2] = lazy[i];
            lazy[i*2+1] = lazy[i];
        }
        lazy[i] = {-INF,-INF};
    }
}

void update(pair<int,int> v, int l, int r, int tl = 0, int tr = N-1, int i = 1) {
    pushdown(tl, tr, i);
    if (l > r) return;
    if (tl == l && tr == r) {
        lazy[i] = v;
        pushdown(tl, tr, i);
        return;
    }
    int tm = (tl + tr) / 2;
    update(v, l, min(r, tm), tl, tm, i * 2);
    update(v, max(l, tm + 1), r, tm + 1, tr, i * 2 + 1);
}

int query(int p, int tl = 0, int tr = N-1, int i = 1) {
    pushdown(tl, tr, i);
    if (tl == tr) return tree[i];
    int tm = (tl + tr) / 2;
    if (p <= tm) return query(p, tl, tm, i * 2);
    else return query(p, tm + 1, tr, i * 2 + 1);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    N = n;
    tree.resize(4*N);
    lazy.resize(4*N, {-INF, -INF});
    FOR(i,k) {
        update({height[i], op[i]}, left[i], right[i]);
    }
    FOR(i,n) {
        finalHeight[i] = query(i,i);
    }
}

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