oj.uz

Submission #427601

# Submission time Handle Problem Language Result Execution time Memory
427601 2021-06-14T17:41:50 Z illyakr Wall (IOI14_wall) C++14
100 / 100
 1219 ms 174296 KB 
#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, true};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 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 10 ms 1100 KB Output is correct
5 Correct 7 ms 1228 KB Output is correct
6 Correct 10 ms 1228 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 173 ms 8132 KB Output is correct
3 Correct 313 ms 4952 KB Output is correct
4 Correct 1102 ms 25308 KB Output is correct
5 Correct 331 ms 26428 KB Output is correct
6 Correct 319 ms 24772 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 10 ms 1184 KB Output is correct
5 Correct 7 ms 1216 KB Output is correct
6 Correct 7 ms 1228 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 172 ms 13980 KB Output is correct
9 Correct 353 ms 8772 KB Output is correct
10 Correct 1079 ms 25312 KB Output is correct
11 Correct 335 ms 26332 KB Output is correct
12 Correct 319 ms 24800 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 184 ms 14008 KB Output is correct
15 Correct 52 ms 2764 KB Output is correct
16 Correct 1066 ms 25572 KB Output is correct
17 Correct 337 ms 25028 KB Output is correct
18 Correct 321 ms 25044 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 424 KB Output is correct
4 Correct 12 ms 1100 KB Output is correct
5 Correct 7 ms 1228 KB Output is correct
6 Correct 7 ms 1256 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 197 ms 13888 KB Output is correct
9 Correct 335 ms 8748 KB Output is correct
10 Correct 1054 ms 25312 KB Output is correct
11 Correct 361 ms 26404 KB Output is correct
12 Correct 326 ms 24804 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 175 ms 13848 KB Output is correct
15 Correct 53 ms 2768 KB Output is correct
16 Correct 1052 ms 25540 KB Output is correct
17 Correct 361 ms 24960 KB Output is correct
18 Correct 323 ms 25048 KB Output is correct
19 Correct 1120 ms 174296 KB Output is correct
20 Correct 1099 ms 171684 KB Output is correct
21 Correct 1101 ms 174292 KB Output is correct
22 Correct 1082 ms 171672 KB Output is correct
23 Correct 1140 ms 171748 KB Output is correct
24 Correct 1091 ms 171696 KB Output is correct
25 Correct 1082 ms 171812 KB Output is correct
26 Correct 1156 ms 174248 KB Output is correct
27 Correct 1190 ms 174176 KB Output is correct
28 Correct 1219 ms 171712 KB Output is correct
29 Correct 1158 ms 171736 KB Output is correct
30 Correct 1090 ms 171952 KB Output is correct