oj.uz

Submission #832280

# Submission time Handle Problem Language Result Execution time Memory
832280 2023-08-21T08:24:37 Z JoenPoenMan Wall (IOI14_wall) C++17
24 / 100
 501 ms 27668 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;
#define INF 1e6

struct Tree {
    int l, r, v = 0, lazyAdd = -1, lazyRem = INF;
    bool addFirst = true;
    Tree *lptr = NULL, *rptr = NULL;

    Tree(int n) : l(0), r(n-1) {};
    Tree(int _l, int _r) : l(_l), r(_r) {};

    void push(Tree *p) {
        int p_lazyAdd = p->lazyAdd, p_lazyRem = p->lazyRem;
        bool p_addFirst = p->addFirst;

        if (lazyAdd == -1 && lazyRem == INF) {
            lazyAdd = p_lazyAdd;
            lazyRem = p_lazyRem;
            addFirst = p_addFirst;
        } else if (p_lazyAdd == -1 && p_lazyRem == INF) {
            return;
        }

        else if (p_lazyAdd > p_lazyRem) {
            lazyAdd = p_lazyAdd;
            lazyRem = p_lazyRem;
            addFirst = lazyAdd;
        } else if (lazyAdd > lazyRem) {
            int val = (p_addFirst ? lazyRem : lazyAdd);
            lazyAdd = max((p_addFirst ? val : min(val, p_lazyRem)), p_lazyAdd);
            lazyRem = min((p_addFirst ? max(val, p_lazyAdd) : val), p_lazyRem);
            addFirst = p_addFirst;
        } 
        
        else if (addFirst && ! p_addFirst) {
            lazyRem = min(lazyRem, p_lazyRem);
            lazyAdd = max(p_lazyAdd, min(lazyAdd, lazyRem));
            addFirst = false;
        } else if (!addFirst && p_addFirst) {
            lazyAdd = max(lazyAdd, p_lazyAdd);
            lazyRem = min(p_lazyRem, max(lazyRem, lazyAdd));
            addFirst = true;
        }

        else if (addFirst && p_addFirst) {
            lazyAdd = max(p_lazyAdd, lazyAdd);
            lazyRem = min(p_lazyRem, max(lazyRem, p_lazyAdd));
            addFirst = true;
        } else if (!addFirst && !p_addFirst) {
            lazyRem = min(p_lazyRem, lazyRem);
            lazyAdd = max(p_lazyAdd, min(lazyAdd, p_lazyRem));
            addFirst = false;
        }
    }

    void processLazy() {
        if (addFirst) {
            v = max(v, lazyAdd);
        }
        v = min(v, lazyRem);
        if (!addFirst) {
            v = max(v, lazyAdd);
        }
        lazyAdd = -1;
        lazyRem = INF;
    }

    void opp(int a, int b, int op, int h) {
        if (a > b) return;
        if (a == l && b == r) {
            if      ( addFirst && op == 2) lazyRem = min(lazyRem, h);
            else if (!addFirst && op == 1) lazyAdd = max(lazyAdd, h);
            else if (op == 2) {
                lazyRem = min(h, max(lazyRem, lazyAdd));
                addFirst = true;
            }
            else if (op == 1) {
                lazyAdd = max(h, min(lazyRem, lazyAdd));
                addFirst = false;
            }
            if (l == r) processLazy();
            return;
        }
        if (l == r) {
            processLazy();
            return;
        }
        int mid = (l + r)/2;
        if (lptr == NULL) {
            lptr = new Tree(l, mid);
            rptr = new Tree(mid + 1, r);
        }
        lptr->push(this);
        rptr->push(this);
        lazyAdd = -1, lazyRem = INF;
        lptr->opp(a, min(mid, b), op, h);
        rptr->opp(max(mid+1, a), b, op, h);
    }

    void readAll(int finalHeight[]) {
        if (lptr == NULL) {
            processLazy();
            for (int i = l; i <= r; i++) {
                finalHeight[i] = v;
            }
            return;
        }
        lptr->push(this);
        rptr->push(this);
        lptr->readAll(finalHeight);
        rptr->readAll(finalHeight);
    }


};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    Tree *t = new Tree(n);
    for (int i = 0; i < k; i++) {
        t->opp(left[i], right[i], op[i], height[i]);
    }
    t->readAll(finalHeight);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 101 ms 13896 KB Output is correct
3 Correct 159 ms 9092 KB Output is correct
4 Correct 501 ms 27668 KB Output is correct
5 Correct 222 ms 26608 KB Output is correct
6 Correct 240 ms 25040 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 312 KB Output isn't correct
4 Halted 0 ms 0 KB -