Submission #427584

#	Time	Username	Problem	Language	Result	Execution time	Memory
427584		illyakr	Wall (IOI14_wall)	C++14	0 / 100	3095 ms	8176 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
struct Info {
    int add;
    int del;
    int press;
    /**
    ADD can't be more than DEL
    ADD < DEL
    */

    bool have;
};

int t[8000001];
Info tAdd[8000001];

void tr(Info &NEED, Info &gov) {
    if (!gov.have)return;

    if (!NEED.have){NEED = gov;return;}
    if (gov.press != -1) {NEED = {-1, -1, gov.press, 0};return;}
    if (NEED.press != -1) {
        if (gov.add != -1)NEED.press = max(NEED.press, gov.add);
        if (gov.del != -1)NEED.press = min(NEED.press, gov.del);
        return;
    }
    if (NEED.add == -1 && NEED.del != -1) {
        if (gov.del != -1)NEED.del = min(NEED.del, gov.del);
        if (gov.add != -1) {
            if (NEED.del <= gov.add) {
                NEED = {-1, -1, gov.add, true};
            } else {
                NEED.add = gov.add;
            }
        }
        return;
    }
    if (NEED.add != -1 && NEED.del == -1) {
        if (gov.add != -1)NEED.add = max(NEED.add, gov.add);
        if (gov.del != -1) {
            if (NEED.add >= gov.del) {
                NEED = {-1, -1, gov.del, true};
            } else {
                NEED.del = gov.del;
            }
        }
        return;
    }
    if (NEED.add != -1 && NEED.del != -1) {
        /**
            NEED.add < NEED.del <= gov.add < gov.del
            gov.add < gov.del <= NEED.add < NEED.del

            NEED.add <= gov.add < gov.del <= NEED.del
            gov.add <= NEED.add < NEED.del <= gov.del

            NEED.add <= gov.add < NEED.del <= gov.del
            NEED.add < gov.add <= NEED.del < gov.del
            gov.add <= NEED.add < gov.del <= NEED.del
            gov.add < NEED.add <= gov.del < NEED.del
        */
        if (gov.add != -1 && gov.del == -1) {
            if (NEED.del <= gov.add) {
                NEED = {-1, -1, gov.add, true};
            } else {
                NEED.add = max(NEED.add, gov.add);
            }
        } else if (gov.add == -1 && gov.del != -1) {
            if (gov.del <= NEED.add) {
                NEED = {-1, -1, gov.del, true};
            } else {
                NEED.del = min(NEED.del, gov.del);
            }
        } else {
            if (NEED.del <= gov.add) {
                NEED = {-1, -1, gov.add, true};
            } else if (gov.del <= NEED.add) {
                NEED = {-1, -1, gov.del, true};
            } else {
                NEED.add = max(NEED.add, gov.add);
                NEED.del = min(NEED.del, gov.del);
            }
        }
        return;
    }
    exit(1);
    return;
}

void push(int v, int vl, int vr) {
    if (!tAdd[v].have)return;
    if (vl == vr) {
        if (tAdd[v].press != -1) {
            t[v] = tAdd[v].press;
        } else {
            if (tAdd[v].del != -1)t[v] = min(t[v], tAdd[v].del);
            if (tAdd[v].add != -1)t[v] = max(t[v], tAdd[v].add);
        }
    } else {
        tr(tAdd[2 * v], tAdd[v]);
        tr(tAdd[2 * v + 1], tAdd[v]);
    }


    tAdd[v].add = -1;
    tAdd[v].del = -1;
    tAdd[v].press = -1;
    tAdd[v].have = false;
}
void upd(int v, int vl, int vr, int l, int r, int val, int ty) {
    push(v, vl, vr);
    if (l <= vl && vr <= r) {
        Info go;
        if (ty == 1)go = {val, -1, -1, true};
        if (ty == 2)go = {-1, val, -1, true};
        tr(tAdd[v], go);
        push(v, vl, vr);
        return;
    }
    if (r < vl || vr < l)return;
    int vm = (vl + vr) / 2;
    upd(2 * v, vl, vm, l, r, val, ty);
    upd(2 * v + 1, vm + 1, vr, l, r, val, ty);
}
int gt(int v, int vl, int vr, int pos) {
    push(v, vl, vr);
    if (vl == vr)return t[v];
    int vm = (vl + vr) / 2;
    if (pos <= vm)return gt(2 * v, vl, vm, pos);
    return gt(2 * v + 1, vm + 1, vr, pos);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 1; i <= 4*n; i++) {
        tAdd[i].add = -1;
        tAdd[i].del = -1;
        tAdd[i].press = -1;
        tAdd[i].have = false;
    }
    for (int id = 0; id < k; id++) {
        upd(1, 1, n, left[id] + 1, right[id] + 1, height[id], op[id]);
        for (int j = 1; j <= n; j++) {
            gt(1, 1, n, j);
        }
    }
    for (int i = 1; i <= n; i++)
        finalHeight[i - 1] = gt(1, 1, n, i);
}

/**
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
*/

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