oj.uz

Submission #939733

# Submission time Handle Problem Language Result Execution time Memory
939733 2024-03-06T17:19:45 Z asdasdqwer Wall (IOI14_wall) C++14
0 / 100
 1 ms 348 KB 
#include "wall.h"

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


int le;
vector<int> lzMin, lzMax;
const int minConst = 1e9;
const int maxConst = 0;

void init (int sz) {
    le=1;
    while(le<sz)le*=2;
    lzMin.assign(2*le, minConst);
    lzMax.assign(2*le, maxConst);
}

void pushdown(int x) {
    if (lzMin[x] == minConst && lzMax[x] == maxConst) {
        return;
    }

    lzMin[2*x+1] = min(max(lzMax[x], lzMin[2*x+1]), lzMin[x]);
    lzMin[2*x+2] = min(max(lzMax[x], lzMin[2*x+2]), lzMin[x]);
    lzMax[2*x+1] = max(min(lzMin[x], lzMax[2*x+1]), lzMax[x]);
    lzMax[2*x+2] = max(min(lzMin[x], lzMax[2*x+2]), lzMax[x]);

    lzMin[x] = minConst;
    lzMax[x] = maxConst;
}

void setVal(int l, int r, int v, int x, int lx, int rx, bool isMax=false) {
    if (lx >= r || rx <= l) return;
    if (rx - lx == 1) {
        if (isMax) {
            if (lzMax[x] < v) {
                lzMax[x] = v;
            }

            if (lzMin[x] < v) {
                lzMin[x] = v;
            }
        }

        else {
            if (lzMin[x] > v) {
                lzMin[x] = v;
            }

            if (lzMax[x] > v) {
                lzMax[x] = v;
            }
        }

        return;
    }

    pushdown(x);
    
    if (lx >= l && rx <= r) {
        if (isMax) {
            if (lzMax[x] < v) {
                lzMax[x] = v;
            }

            if (lzMin[x] < v) {
                lzMin[x] = v;
            }
        }

        else {
            if (lzMin[x] > v) {
                lzMin[x] = v;
            }

            if (lzMax[x] > v) {
                lzMax[x] = v;
            }
        }
        return;
    }

    int m=(lx+rx)/2;
    setVal(l, r, v, 2*x+1, lx, m, isMax);
    setVal(l, r, v, 2*x+2, m, rx, isMax);
}

void setMax(int l, int r, int v) {
    setVal(l, r, v, 0, 0, le, true);
}

void setMin(int l, int r, int v) {
    setVal(l, r, v, 0, 0, le, false);
}

int get(int i, int x, int lx, int rx) {
    if (rx-lx==1) {
        return lzMax[x];
    }

    pushdown(x);
    int m=(lx+rx)/2;
    if (i<m)return get(i,2*x+1,lx,m);
    else return get(i,2*x+2,m,rx);
}

int get(int i) {
    return get(i,0,0,le);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (int i=0;i<k;i++) {
        if (op[i] == 1) {
            setMax(left[i], right[i]+1, height[i]);
        }

        else {
            setMin(left[i], right[i]+1, height[i]);
        }
    }

    for (int i=0;i<n;i++) {
        finalHeight[i] = get(i);
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -