oj.uz

Submission #1019437

# Submission time Handle Problem Language Result Execution time Memory
1019437 2024-07-10T20:41:51 Z n3rm1n Wall (IOI14_wall) C++17
61 / 100
 307 ms 36688 KB 
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 1e5 + 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 2 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 4 ms 5552 KB Output is correct
5 Correct 7 ms 5464 KB Output is correct
6 Correct 4 ms 5468 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 79 ms 12992 KB Output is correct
3 Correct 46 ms 8788 KB Output is correct
4 Correct 124 ms 23324 KB Output is correct
5 Correct 184 ms 24548 KB Output is correct
6 Correct 154 ms 22824 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 4 ms 5468 KB Output is correct
6 Correct 4 ms 5468 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 80 ms 18948 KB Output is correct
9 Correct 48 ms 12368 KB Output is correct
10 Correct 116 ms 23376 KB Output is correct
11 Correct 192 ms 24356 KB Output is correct
12 Correct 154 ms 23012 KB Output is correct
13 Correct 2 ms 5208 KB Output is correct
14 Correct 83 ms 18952 KB Output is correct
15 Correct 19 ms 6484 KB Output is correct
16 Correct 307 ms 23760 KB Output is correct
17 Correct 213 ms 23124 KB Output is correct
18 Correct 188 ms 23120 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 4 ms 5496 KB Output is correct
5 Correct 4 ms 5548 KB Output is correct
6 Correct 4 ms 5464 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 81 ms 18964 KB Output is correct
9 Correct 49 ms 12372 KB Output is correct
10 Correct 115 ms 23536 KB Output is correct
11 Correct 194 ms 24504 KB Output is correct
12 Correct 189 ms 22868 KB Output is correct
13 Correct 2 ms 5208 KB Output is correct
14 Correct 83 ms 18928 KB Output is correct
15 Correct 19 ms 6488 KB Output is correct
16 Correct 298 ms 23812 KB Output is correct
17 Correct 193 ms 23124 KB Output is correct
18 Correct 187 ms 23120 KB Output is correct
19 Runtime error 107 ms 36688 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -