oj.uz

Submission #287188

# Submission time Handle Problem Language Result Execution time Memory
287188 2020-08-31T13:23:07 Z Atill83 Wall (IOI14_wall) C++14
100 / 100
 1032 ms 135584 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->lazy1;
    }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->lazy2;
        cur->l->lazy2 = cur->lazy2;
    }

    if(cur->lazy1 >= cur->r->lazy2){
        cur->r->lazy1 = cur->lazy1;
        cur->r->lazy2 = cur->lazy1;
    }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->lazy2;
        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;
    else if(tl == ll && tr == rr){
        if(op == 1){
            if(dg >= cur->lazy2){
                cur->lazy2 = dg;
                cur->lazy1 = dg;
            }else if(dg > cur->lazy1){
                cur->lazy1 = dg;
            }
            cur->deg = max(cur->deg, dg);
        }else{
            if(dg <= cur->lazy1){
                cur->lazy1 = dg;
                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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 9 ms 1408 KB Output is correct
5 Correct 6 ms 1280 KB Output is correct
6 Correct 7 ms 1280 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 177 ms 8208 KB Output is correct
3 Correct 246 ms 5368 KB Output is correct
4 Correct 724 ms 18168 KB Output is correct
5 Correct 372 ms 18936 KB Output is correct
6 Correct 353 ms 18936 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 1408 KB Output is correct
5 Correct 6 ms 1280 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 177 ms 10232 KB Output is correct
9 Correct 233 ms 7416 KB Output is correct
10 Correct 712 ms 20528 KB Output is correct
11 Correct 374 ms 19064 KB Output is correct
12 Correct 350 ms 18808 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 180 ms 10488 KB Output is correct
15 Correct 41 ms 3064 KB Output is correct
16 Correct 823 ms 20856 KB Output is correct
17 Correct 367 ms 18552 KB Output is correct
18 Correct 367 ms 18552 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 1408 KB Output is correct
5 Correct 7 ms 1280 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 177 ms 10124 KB Output is correct
9 Correct 236 ms 7416 KB Output is correct
10 Correct 683 ms 20344 KB Output is correct
11 Correct 368 ms 18808 KB Output is correct
12 Correct 355 ms 18808 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 182 ms 10488 KB Output is correct
15 Correct 42 ms 3064 KB Output is correct
16 Correct 856 ms 20852 KB Output is correct
17 Correct 383 ms 19108 KB Output is correct
18 Correct 377 ms 19064 KB Output is correct
19 Correct 971 ms 135544 KB Output is correct
20 Correct 975 ms 132752 KB Output is correct
21 Correct 965 ms 135448 KB Output is correct
22 Correct 945 ms 133020 KB Output is correct
23 Correct 1032 ms 132896 KB Output is correct
24 Correct 987 ms 132844 KB Output is correct
25 Correct 956 ms 133184 KB Output is correct
26 Correct 968 ms 135584 KB Output is correct
27 Correct 951 ms 135528 KB Output is correct
28 Correct 963 ms 132844 KB Output is correct
29 Correct 951 ms 133472 KB Output is correct
30 Correct 941 ms 133580 KB Output is correct