oj.uz

Submission #794765

# Submission time Handle Problem Language Result Execution time Memory
794765 2023-07-26T22:14:20 Z idiotcomputer Wall (IOI14_wall) C++11
0 / 100
 119 ms 13912 KB 
#include "wall.h"

const int MAX_N = 20000;
const int NINF = -1 * (1 << 30);
const int INF = (1<<30);

struct node {
    int tmin = -1;
    int tmax = -1;
    int opmin = INF;
    int opmax = NINF;
};

node segt[4*MAX_N+1];
void upd(int l, int r, int idx, int tl, int tr, int w, int h, int t){
    if (l > tr || r < tl){
        return;
    }
    if (l >= tl && r <= tr){
        //mini
        if (w == 1){
            if (h <= segt[idx].opmin || segt[idx].tmin == -1){
                segt[idx].opmin = h;
                segt[idx].tmin = t;
            }            
            if (h <= segt[idx].opmax || segt[idx].tmax == -1){
                segt[idx].opmax = h;
                segt[idx].tmax = t;
            }
        } else {
            if (h >= segt[idx].opmax || segt[idx].tmin == -1){
                segt[idx].opmax = h;
                segt[idx].tmax = t;
            }
            if (h >= segt[idx].opmin || segt[idx].tmax == -1){
                segt[idx].opmin = h;
                segt[idx].tmin = t;
            }
        }
        return;
    }
    int m = (l+r)/2;
    upd(l,m,2*idx+1,tl,tr,w,h,t);
    upd(m+1,r,2*idx+2,tl,tr,w,h,t);
    return;
}

void solve(int l, int r, int idx, int finalHeight[], node a){
    if (segt[idx].opmin <= a.opmax && segt[idx].tmin > a.tmax){
        a.opmax = segt[idx].opmin;
        a.tmax = segt[idx].tmin;
    } 
    if (segt[idx].opmin <= a.opmin && segt[idx].tmin > a.tmin){
        a.tmin = segt[idx].tmin;
        a.opmin = segt[idx].opmin;
    }
    if (segt[idx].opmax >= a.opmax && segt[idx].tmax > a.tmax){
        a.opmax = segt[idx].opmax;
        a.tmax = segt[idx].tmax;
    }
    if (segt[idx].opmax >= a.opmin && segt[idx].tmax > a.tmin){
        a.opmin = segt[idx].opmax;
        a.tmin = segt[idx].tmax;
    }
    if (l == r){
     /*   if (a.opmin != a.opmax){
            cout << "UHOHSPAGHETIIO "  << l << ' ' << r << " " << idx << " " << a.opmin << " " << a.opmax << '\n';
        }*/
        if (a.opmin == INF && a.opmax == NINF){
            finalHeight[l] = 0;
        } else if (a.opmin == INF){
            finalHeight[l] = a.opmax;
        } else if (a.opmax == INF){
            finalHeight[l] = a.opmin;
        } else {
            finalHeight[l] = a.opmin;
        }
        return;
    }
    int m = (l+r)/2;
    solve(l,m,2*idx+1,finalHeight,a);
    solve(m+1,r,2*idx+2,finalHeight,a);
    return;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    int l,r,w,h,idx;
    for (int i =0; i < k; i++){
        w = op[i]-1;
        h = height[i];
        idx = i;
        l = left[i];
        r = right[i];
        upd(0,n-1,0,l,r,w,h,idx);
    }
    
    node a;
    solve(0,n-1,0,finalHeight,a);
    return;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 29.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 304 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 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -