oj.uz

Submission #287170

# Submission time Handle Problem Language Result Execution time Memory
287170 2020-08-31T13:05:06 Z Atill83 Wall (IOI14_wall) C++14
0 / 100
 726 ms 19960 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
const int MAXN = (int) 2e6 + 5;
typedef pair<int, int> pii;
int * an;
const int inf = (int) 1e6;
struct node{
    int deg = 0, lazy1 = 0, lazy2 = inf;
    node * l = NULL;
    node * r = NULL;
};
typedef node * pn;

void push(pn cur){
    cur->l->deg = max(cur->l->deg, cur->lazy1);
    cur->l->deg = min(cur->l->deg, cur->lazy2);
    cur->r->deg = max(cur->r->deg, cur->lazy1);
    cur->r->deg = min(cur->r->deg, cur->lazy2);
    if(cur->lazy1 >= cur->l->lazy2){
        cur->l->lazy1 = cur->lazy1;
        cur->l->lazy2 = cur->lazy2;
    }else if(cur->lazy1 >= cur->l->lazy1){
        cur->l->lazy1 = cur->lazy1;
        cur->l->lazy2 = min(cur->l->lazy2, cur->lazy2);
    }else if(cur->lazy2 >= cur->l->lazy1){
        cur->l->lazy2 = min(cur->l->lazy2, cur->lazy2);
    }else{
        cur->l->lazy1 = cur->lazy1;
        cur->l->lazy2 = cur->lazy2;
    }

    if(cur->lazy1 >= cur->r->lazy2){
        cur->r->lazy1 = cur->lazy1;
        cur->r->lazy2 = cur->lazy2;
    }else if(cur->lazy1 >= cur->r->lazy1){
        cur->r->lazy1 = cur->lazy1;
        cur->r->lazy2 = min(cur->r->lazy2, cur->lazy2);
    }else if(cur->lazy2 >= cur->r->lazy1){
        cur->r->lazy2 = min(cur->r->lazy2, cur->lazy2);
    }else{
        cur->r->lazy1 = cur->lazy1;
        cur->r->lazy2 = cur->lazy2;
    }

    cur->lazy1 = 0;
    cur->lazy2 = inf;
}


void upd(pn cur, int tl, int tr, int ll, int rr, int dg, int op){
    if(ll > rr) return;
    if(tl == ll && tr == rr){
        if(op == 1){
            if(dg > cur->lazy2){
                cur->lazy2 = inf;
                cur->lazy1 = dg;
            }else if(dg > cur->lazy1){
                cur->lazy1 = dg;
            }
            cur->deg = max(cur->deg, dg);
        }else{
            if(dg < cur->lazy1){
                cur->lazy1 = 0;
                cur->lazy2 = dg;
            }else if(dg < cur->lazy2){
                cur->lazy2 = dg;
            }
            cur->deg = min(cur->deg, dg);
        }
    }else{
        int tm = (tl + tr) / 2;
        if(cur->l == NULL){
            cur->l = new node;
            cur->r = new node;
            cur->l->deg = cur->deg;
            cur->r->deg = cur->deg;
        }
        push(cur);
        upd(cur->l, tl, tm, ll, min(tm, rr), dg, op);
        upd(cur->r, tm + 1, tr, max(ll, tm + 1), rr, dg, op);
    }
}

void fina(pn cur, int tl , int tr){
    if(cur->l == NULL){
        for(int i = tl; i <= tr; i++){
            an[i] = cur->deg;
        }
    }else{
        push(cur);
        int tm = (tl + tr) / 2;
        fina(cur->l, tl, tm);
        fina(cur->r, tm + 1, tr);
    }
}



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    pn root = new node;
    root->deg = 0;
    an = finalHeight;
    for(int i = 0; i < k; i++){
        upd(root, 0, n - 1, left[i], right[i], height[i], op[i]);
    }
    fina(root, 0, n - 1);
    return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Incorrect 2 ms 384 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 256 KB Output is correct
2 Correct 174 ms 9848 KB Output is correct
3 Correct 232 ms 6904 KB Output is correct
4 Incorrect 726 ms 19960 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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