oj.uz

Submission #1019440

# Submission time Handle Problem Language Result Execution time Memory
1019440 2024-07-10T20:44:38 Z n3rm1n Wall (IOI14_wall) C++17
100 / 100
 505 ms 138560 KB 
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 2e6 + 10;

struct node
{
    int minval, maxval, lazy;
    node()
    {
        minval = 0;
        maxval = 0;
        lazy = -1;
    }
};


node t[MAXN * 4];

void push_lazy(int i, int l, int r)
{
    if(t[i].lazy == -1)return;

        t[i].minval = t[i].lazy;
        t[i].maxval = t[i].lazy;

    if(l != r)
    {
        t[2*i].lazy = t[i].lazy;
        t[2*i+1].lazy = t[i].lazy;
    }
    t[i].lazy = -1;
}

int ql, qr, x;
void upd_minimum(int i, int l, int r)
{
    push_lazy(i, l, r);
    if(ql > r || qr < l)return;

    if(t[i].maxval <= x)return;
    if(ql <= l && r <= qr)
    {
        //if(t[i].maxval <= x)return;
        if(t[i].minval > x)
        {
            t[i].lazy = x;
            push_lazy(i, l, r);
            return;
        }
      // else return;
    }
    if(l == r)return;
    int mid = (l + r)/2;
    upd_minimum(2*i, l, mid);
    upd_minimum(2*i+1, mid+1, r);

    t[i].minval = min(t[2*i].minval, t[2*i+1].minval);
    t[i].maxval = max(t[2*i].maxval, t[2*i+1].maxval);
}

void upd_maximum(int i, int l, int r)
{
    push_lazy(i, l, r);
    if(ql > r || qr < l)return;

    if(t[i].minval >= x)return;
    if(ql <= l && r <= qr)
    {

        if(t[i].maxval < x)
        {
            t[i].lazy = x;
            push_lazy(i, l, r);
            return;
        }
       //else return;
    }
    if(l == r)return;
    int mid = (l + r)/2;
    upd_maximum(2*i, l, mid);
    upd_maximum(2*i+1, mid+1, r);

    t[i].minval = min(t[2*i].minval, t[2*i+1].minval);
    t[i].maxval = max(t[2*i].maxval, t[2*i+1].maxval);
}

int h[MAXN];
void build(int i, int l, int r)
{
    push_lazy(i, l, r);
    if(l == r)
    {
        h[l] = t[i].minval;
        return;
    }
    int mid = (l + r)/2;
    build(2*i, l, mid);
    build(2*i+1, mid+1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for (int i = 0; i < k; ++ i)
    {
        ql = left[i] + 1;
        qr = right[i] + 1;
        x = height[i];
        if(op[i] == 1)
            upd_maximum(1, 1, n);
        else upd_minimum(1, 1, n);
    }
    build(1, 1, n);
    for (int i = 1; i <= n; ++ i)
        finalHeight[i-1] = h[i];
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 94288 KB Output is correct
2 Correct 37 ms 94300 KB Output is correct
3 Correct 36 ms 94192 KB Output is correct
4 Correct 39 ms 94548 KB Output is correct
5 Correct 38 ms 94556 KB Output is correct
6 Correct 39 ms 94552 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 94300 KB Output is correct
2 Correct 124 ms 107628 KB Output is correct
3 Correct 89 ms 101460 KB Output is correct
4 Correct 149 ms 111952 KB Output is correct
5 Correct 146 ms 112720 KB Output is correct
6 Correct 165 ms 111444 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 94160 KB Output is correct
2 Correct 37 ms 94360 KB Output is correct
3 Correct 36 ms 94288 KB Output is correct
4 Correct 39 ms 94548 KB Output is correct
5 Correct 39 ms 94544 KB Output is correct
6 Correct 39 ms 94448 KB Output is correct
7 Correct 36 ms 94300 KB Output is correct
8 Correct 115 ms 107448 KB Output is correct
9 Correct 82 ms 101208 KB Output is correct
10 Correct 149 ms 112208 KB Output is correct
11 Correct 152 ms 112692 KB Output is correct
12 Correct 160 ms 111444 KB Output is correct
13 Correct 36 ms 94288 KB Output is correct
14 Correct 118 ms 107536 KB Output is correct
15 Correct 57 ms 95824 KB Output is correct
16 Correct 337 ms 112196 KB Output is correct
17 Correct 239 ms 111808 KB Output is correct
18 Correct 221 ms 111844 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 94288 KB Output is correct
2 Correct 37 ms 94496 KB Output is correct
3 Correct 36 ms 94300 KB Output is correct
4 Correct 39 ms 94548 KB Output is correct
5 Correct 40 ms 94800 KB Output is correct
6 Correct 38 ms 94548 KB Output is correct
7 Correct 34 ms 94292 KB Output is correct
8 Correct 115 ms 107940 KB Output is correct
9 Correct 82 ms 101456 KB Output is correct
10 Correct 157 ms 112620 KB Output is correct
11 Correct 150 ms 113488 KB Output is correct
12 Correct 166 ms 111952 KB Output is correct
13 Correct 40 ms 94288 KB Output is correct
14 Correct 118 ms 107856 KB Output is correct
15 Correct 53 ms 95568 KB Output is correct
16 Correct 334 ms 112720 KB Output is correct
17 Correct 229 ms 112212 KB Output is correct
18 Correct 225 ms 112212 KB Output is correct
19 Correct 463 ms 138304 KB Output is correct
20 Correct 452 ms 136016 KB Output is correct
21 Correct 499 ms 138396 KB Output is correct
22 Correct 435 ms 135836 KB Output is correct
23 Correct 459 ms 135852 KB Output is correct
24 Correct 454 ms 136012 KB Output is correct
25 Correct 468 ms 136016 KB Output is correct
26 Correct 484 ms 138492 KB Output is correct
27 Correct 476 ms 138560 KB Output is correct
28 Correct 505 ms 136016 KB Output is correct
29 Correct 493 ms 135936 KB Output is correct
30 Correct 486 ms 136016 KB Output is correct