oj.uz

Submission #1016590

# Submission time Handle Problem Language Result Execution time Memory
1016590 2024-07-08T08:36:51 Z n3rm1n Wall (IOI14_wall) C++17
32 / 100
 231 ms 22612 KB 
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 1e5 + 10;
int nn, kk;
int lazy_max[4 * MAXN], lazy_min[4 * MAXN];
int add[MAXN], rem[MAXN];
int ql, qr, h;

void makeit(int i, int l, int r)
{
    lazy_max[i] = -1;
    lazy_min[i] = 1e6;
    if(l == r)
    {
        return;
    }
    int mid = (l + r)/2;
    makeit(2*i, l, mid);
    makeit(2*i+1, mid+1, r);

}
void update_maxx(int i, int l, int r)
{
    if(ql <= l && r <= qr)
    {
        lazy_max[i] = max(lazy_max[i], h);
        return;
    }
    if(ql > r || qr < l)
        return;
    int mid = (l + r)/2;
    update_maxx(2*i, l, mid);
    update_maxx(2*i+1, mid+1, r);
}

void update_minn(int i, int l, int r)
{
    if(ql <= l && r <= qr)
    {
        lazy_min[i] = min(lazy_min[i], h);
        return;
    }
    if(ql > r || qr < l)
        return;
    int mid = (l + r)/2;
    update_minn(2*i, l, mid);
    update_minn(2*i+1, mid+1, r);
}
void build_add(int i, int l, int r, int move_down)
{
    if(l == r)
    {
        add[l] = max(lazy_max[i], move_down);
        return ;
    }
    int mid = (l + r)/2;

    build_add(2*i, l, mid, max(move_down, lazy_max[i]));
    build_add(2*i+1, mid+1, r, max(move_down, lazy_max[i]));
}
void build_rem(int i, int l, int r, int move_down)
{
    if(l == r)
    {
        rem[l] = min(lazy_min[i], move_down);
        return;
    }
    int mid = (l + r)/2;

    build_rem(2*i, l, mid, min(move_down, lazy_min[i]));
    build_rem(2*i+1, mid+1, r, min(move_down, lazy_min[i]));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    if(n <= 10000)
    {
        for (int i = 0; i < k; ++ i)
        {

            for (int j = left[i]; j <= right[i]; ++ j)
            {
                if(op[i] == 1)finalHeight[j] = max(finalHeight[j], height[i]);
                else finalHeight[j] = min(finalHeight[j], height[i]);
            }
        }
        return;
    }
    makeit(1, 0, n-1);
    for (int i = 0; i < k; ++ i)
    {
        ql = left[i];
        qr = right[i];
        h = height[i];
        if(op[i] == 1)
        {
            update_maxx(1, 0, n-1);
        }
        else update_minn(1, 0, n-1);
    }
    build_add(1, 0, n-1, -1);
    build_rem(1, 0, n-1, 1e6);
    for (int i = 0; i < n; ++ i)
    {
        finalHeight[i] = max(0, add[i]);
        finalHeight[i] = min(finalHeight[i], rem[i]);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 14 ms 556 KB Output is correct
5 Correct 14 ms 600 KB Output is correct
6 Correct 14 ms 556 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 82 ms 8104 KB Output is correct
3 Correct 87 ms 6108 KB Output is correct
4 Correct 231 ms 11912 KB Output is correct
5 Correct 153 ms 22612 KB Output is correct
6 Correct 148 ms 21072 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 13 ms 604 KB Output is correct
5 Correct 13 ms 604 KB Output is correct
6 Correct 13 ms 600 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 80 ms 8032 KB Output is correct
9 Correct 81 ms 5996 KB Output is correct
10 Correct 212 ms 12116 KB Output is correct
11 Correct 150 ms 22608 KB Output is correct
12 Correct 136 ms 21072 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 86 ms 13916 KB Output is correct
15 Incorrect 15 ms 3816 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 13 ms 552 KB Output is correct
5 Correct 14 ms 564 KB Output is correct
6 Correct 14 ms 556 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 106 ms 8136 KB Output is correct
9 Correct 81 ms 6064 KB Output is correct
10 Correct 220 ms 12112 KB Output is correct
11 Correct 152 ms 22608 KB Output is correct
12 Correct 138 ms 21072 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 81 ms 14092 KB Output is correct
15 Incorrect 14 ms 3928 KB Output isn't correct
16 Halted 0 ms 0 KB -