Submission #391521

#	Time	Username	Problem	Language	Result	Execution time	Memory
391521		Aldas25	Wall (IOI14_wall)	C++14	100 / 100	1010 ms	102416 KiB

wall

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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAXN = 2000100;
const int INF = 1e9;

int tree[2][4*MAXN], lazy[2][4*MAXN];
int n;

void build (int id = 1, int le = 0, int ri = n-1) {
    if (le == ri) {
        tree[0][id] = lazy[0][id] = -1e9;
        tree[1][id] = lazy[1][id] = 1e9;
        return;
    }
    int mid = (le+ri)/2;
    build (2*id, le, mid);
    build (2*id+1, mid+1, ri);

    tree[0][id] = lazy[0][id] = -INF;
    tree[1][id] = lazy[1][id] = INF;
}

void shift (int id) {
    int a = lazy[0][id], b = lazy[1][id];
    if (a == -INF && b == INF) return;

    FOR(ch, 2*id, 2*id+1) {
       /* cout << "------ shifted a = " << a << " b = " << b << "  id = " << id << " to ch = " << ch << endl;
        cout << "  tree[0] = " << tree[0][ch] << " tree[1] = " << tree[1][ch] << endl;
        cout << "  lazy[0] = " << lazy[0][ch] << " lazy[1] = " << lazy[1][ch] << endl; */

        tree[0][ch] = max(a, tree[0][ch]);
        tree[1][ch] = max(a, tree[1][ch]);
        tree[1][ch] = min(b, tree[1][ch]);
        tree[0][ch] = min(tree[0][ch], tree[1][ch]);

        lazy[0][ch] = max(a, lazy[0][ch]);
        lazy[1][ch] = max(a, lazy[1][ch]);
        lazy[1][ch] = min(b, lazy[1][ch]);
        lazy[0][ch] = min(lazy[0][ch], lazy[1][ch]);

       /* cout << "  tree[0] = " << tree[0][ch] << " tree[1] = " << tree[1][ch] << endl;
        cout << "  lazy[0] = " << lazy[0][ch] << " lazy[1] = " << lazy[1][ch] << endl; */
    }

    lazy[0][id] = -INF;
    lazy[1][id] = INF;
}

int get (int p, int id = 1, int le = 0, int ri = n-1) {
    if (le == ri) {
        int x = 0;
        x = max(x, tree[0][id]);
        x = min(x, tree[1][id]);
        return x;
    }
    shift (id);
    int mid = (le+ri)/2;
    if (p <= mid)
        return get(p, 2*id, le, mid);
    else
        return get(p, 2*id+1, mid+1, ri);
}

void upd (int op, int x, int y, int h, int id = 1, int le = 0, int ri = n-1) {
    if (x > ri || y < le) return;
    if (x <= le && ri <= y) {
        if (op == 1) {
            tree[0][id] = max(tree[0][id], h);
            tree[1][id] = max(tree[1][id], h);
            lazy[0][id] = max(lazy[0][id], h);
            lazy[1][id] = max(lazy[1][id], h);

            lazy[0][id] = min(lazy[0][id], lazy[1][id]);
            tree[0][id] = min(tree[0][id], tree[1][id]);
        } else {
            tree[0][id] = min(tree[0][id], h);
            tree[1][id] = min(tree[1][id], h);
            lazy[0][id] = min(lazy[0][id], h);
            lazy[1][id] = min(lazy[1][id], h);

            lazy[0][id] = min(lazy[0][id], lazy[1][id]);
            tree[0][id] = min(tree[0][id], tree[1][id]);
        }
       /* cout << "--- id = " << id << " le = " << le << " ri = " << ri << endl;
        cout << "  tree[0] = " << tree[0][id] << " tree[1] = " << tree[1][id] << endl;
        cout << "  lazy[0] = " << lazy[0][id] << " lazy[1] = " << lazy[1][id] << endl; */
        return;
    }
    shift (id);
    int mid = (le+ri)/2;
    upd (op, x, y, h, 2*id, le, mid);
    upd (op, x, y, h, 2*id+1, mid+1, ri);
}

void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int ans[]){
    //FOR(i, 0, n-1) ans[i] = height[i];

    n = _n;
    build ();

    FOR(i, 0, k-1) {
        upd (op[i], left[i], right[i], height[i]);

       /* cout << " after op i=" << i << ": ";
        FOR(j, 0, n-1) cout << get(j) << " ";
        cout << endl; */
    }

    FOR(i, 0, n-1) ans[i] = get(i);

    return;
}

/*
###
in:
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412

ans:
0
0
0
39412
39412
39412
48623
48623
48623
48623

###
in:
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

ans:
3
4
5
4
3
3
0
0
1
0



10 4
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3


*/

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