oj.uz

Submission #742183

# Submission time Handle Problem Language Result Execution time Memory
742183 2023-05-15T17:57:13 Z vjudge1 Wall (IOI14_wall) C++17
0 / 100
 157 ms 13820 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

const int INF=INT_MAX;
const int t=(1<<4);

pair<int, int> tree[2*t-1];

void propagate(int x)
{
    if (2*x+2>=2*t-1)
        return;

    tree[2*x+1].first=min(tree[2*x+1].first, tree[x].first);
    tree[2*x+1].second=min(tree[2*x+1].second, tree[2*x+1].first);
    tree[2*x+1].second=max(tree[2*x+1].second, tree[x].second);
    tree[2*x+1].first=max(tree[2*x+1].first, tree[2*x+1].second);

    tree[2*x+2].first=min(tree[2*x+2].first, tree[x].first);
    tree[2*x+2].second=min(tree[2*x+2].second, tree[2*x+2].first);
    tree[2*x+2].second=max(tree[2*x+2].second, tree[x].second);
    tree[2*x+2].first=max(tree[2*x+2].first, tree[2*x+2].second);

    tree[x]={INF, -INF};

    return;
}

void adding(int x, int l, int r, int lt, int rt, int value)
{
    if (r<=lt || l>=rt)
        return;

    propagate(x);

    if (l>=lt && r<=rt)
    {
        tree[x].second=max(tree[x].second, value);
        tree[x].first=max(tree[x].first, tree[x].second);

        return;
    }

    adding(2*x+1, l, (l+r)/2, lt, rt, value);
    adding(2*x+2, (l+r)/2, r, lt, rt, value);

    return;
}

void removing(int x, int l, int r, int lt, int rt, int value)
{
    if (r<=lt || l>=rt)
        return;

    propagate(x);

    if (l>=lt && r<=rt)
    {
        tree[x].first=min(tree[x].first, value);
        tree[x].second=min(tree[x].second, tree[x].first);

        return;
    }

    removing(2*x+1, l, (l+r)/2, lt, rt, value);
    removing(2*x+2, (l+r)/2, r, lt, rt, value);

    return;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for (int i=0; i<2*t-1; i++)
        tree[i]={INF, -INF};
    for (int i=0; i<k; i++)
    {
        if (op[i]==1)
            adding(0, 0, t, left[i], right[i]+1, height[i]);
        if (op[i]==2)
            removing(0, 0, t, left[i], right[i]+1, height[i]);
    }
    for (int i=0; i<2*t-1; i++)
        propagate(i);
    for (int i=0; i<n; i++)
        finalHeight[i]=max(tree[i+t-1].second, 0);

    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 432 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 300 KB Output is correct
2 Correct 157 ms 13820 KB Output is correct
3 Runtime error 66 ms 10808 KB Execution killed with signal 11
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 1 ms 340 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 292 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 -