oj.uz

Submission #46511

# Submission time Handle Problem Language Result Execution time Memory
46511 2018-04-21T08:36:08 Z RayaBurong25_1 Wall (IOI14_wall) C++17
100 / 100
 1115 ms 262144 KB 
#include "wall.h"
#include <vector>
#define INF 1000000007
std::vector<int> V;
typedef struct node node;
struct node
{
    int h;
    int lop, lhmin = 0, lhmax = INF;
};
node Seg[8000005];
int min(int a, int b)
{
    return (a < b)?a:b;
}
int max(int a, int b)
{
    return (a > b)?a:b;
}
void flush(int s, int e, int cell)
{
    int i;
    if (Seg[cell].lop == 1)
    {
        Seg[cell].h = min(Seg[cell].h, Seg[cell].lhmax);
        Seg[cell].h = max(Seg[cell].h, Seg[cell].lhmin);
        if (s != e)
        {
            for (i = 1; i <= 2; i++)
            {
                if (Seg[cell].lhmax < Seg[2*cell + i].lhmin)
                {
                    Seg[2*cell + i].lhmin = Seg[cell].lhmax;
                    Seg[2*cell + i].lhmax = Seg[cell].lhmax;
                }
                else
                    Seg[2*cell + i].lhmax = min(Seg[2*cell + i].lhmax, Seg[cell].lhmax);

                if (Seg[cell].lhmin > Seg[2*cell + i].lhmax)
                {
                    Seg[2*cell + i].lhmin = Seg[cell].lhmin;
                    Seg[2*cell + i].lhmax = Seg[cell].lhmin;
                }
                else
                    Seg[2*cell + i].lhmin = max(Seg[2*cell + i].lhmin, Seg[cell].lhmin);
                Seg[2*cell + i].lop = Seg[cell].lop;
            }
        }
        Seg[cell].lop = 0;
        Seg[cell].lhmin = 0;
        Seg[cell].lhmax = INF;
    }
    else if (Seg[cell].lop == 2)
    {
        Seg[cell].h = max(Seg[cell].h, Seg[cell].lhmin);
        Seg[cell].h = min(Seg[cell].h, Seg[cell].lhmax);
        if (s != e)
        {
            for (i = 1; i <= 2; i++)
            {
                if (Seg[cell].lhmin > Seg[2*cell + i].lhmax)
                {
                    Seg[2*cell + i].lhmin = Seg[cell].lhmin;
                    Seg[2*cell + i].lhmax = Seg[cell].lhmin;
                }
                else
                    Seg[2*cell + i].lhmin = max(Seg[2*cell + i].lhmin, Seg[cell].lhmin);
                Seg[2*cell + i].lop = Seg[cell].lop;

                if (Seg[cell].lhmax < Seg[2*cell + i].lhmin)
                {
                    Seg[2*cell + i].lhmin = Seg[cell].lhmax;
                    Seg[2*cell + i].lhmax = Seg[cell].lhmax;
                }
                else
                    Seg[2*cell + i].lhmax = min(Seg[2*cell + i].lhmax, Seg[cell].lhmax);
            }
        }
        Seg[cell].lop = 0;
        Seg[cell].lhmin = 0;
        Seg[cell].lhmax = INF;
    }
}
void update(int op, int qs, int qe, int h, int s, int e, int cell)
{
    flush(s, e, cell);
    if (qs == s && qe == e)
    {
        if (op == 1)
        {
            if (h > Seg[cell].lhmax)
            {
                Seg[cell].lhmin = h;
                Seg[cell].lhmax = h;
            }
            else
                Seg[cell].lhmin = max(Seg[cell].lhmin, h);
            Seg[cell].lop = op;
        }
        else
        {
            if (h < Seg[cell].lhmin)
            {
                Seg[cell].lhmin = h;
                Seg[cell].lhmax = h;
            }
            else
                Seg[cell].lhmax = min(Seg[cell].lhmax, h);
            Seg[cell].lop = op;
        }
        return;
    }
    int m = (s + e)/2;
    if (qs <= m)
        update(op, qs, min(m, qe), h, s, m, 2*cell + 1);
    if (qe >= m + 1)
        update(op, max(qs, m + 1), qe, h, m + 1, e, 2*cell + 2);
}
void answerAll(int s, int e, int cell)
{
    flush(s, e, cell);
    if (s == e)
    {
        V.push_back(Seg[cell].h);
        return;
    }
    int m = (s + e)/2;
    answerAll(s, m, 2*cell + 1);
    answerAll(m + 1, e, 2*cell + 2);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    int i;
    for (i = 0; i < k; i++)
        update(op[i], left[i], right[i], height[i], 0, n - 1, 0);
    answerAll(0, n - 1, 0);
    for (i = 0; i < n; i++)
        finalHeight[i] = V[i];
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 125484 KB Output is correct
2 Correct 95 ms 125748 KB Output is correct
3 Correct 95 ms 125836 KB Output is correct
4 Correct 116 ms 126164 KB Output is correct
5 Correct 95 ms 126292 KB Output is correct
6 Correct 96 ms 126460 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 126460 KB Output is correct
2 Correct 266 ms 140028 KB Output is correct
3 Correct 309 ms 140028 KB Output is correct
4 Correct 825 ms 154572 KB Output is correct
5 Correct 415 ms 165260 KB Output is correct
6 Correct 370 ms 173812 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 173812 KB Output is correct
2 Correct 94 ms 173812 KB Output is correct
3 Correct 98 ms 173812 KB Output is correct
4 Correct 109 ms 173812 KB Output is correct
5 Correct 103 ms 173812 KB Output is correct
6 Correct 97 ms 173812 KB Output is correct
7 Correct 101 ms 173812 KB Output is correct
8 Correct 274 ms 178580 KB Output is correct
9 Correct 313 ms 178580 KB Output is correct
10 Correct 782 ms 193140 KB Output is correct
11 Correct 406 ms 203876 KB Output is correct
12 Correct 395 ms 212388 KB Output is correct
13 Correct 95 ms 212388 KB Output is correct
14 Correct 275 ms 216900 KB Output is correct
15 Correct 147 ms 216900 KB Output is correct
16 Correct 1115 ms 228308 KB Output is correct
17 Correct 399 ms 237144 KB Output is correct
18 Correct 407 ms 246316 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 246316 KB Output is correct
2 Correct 94 ms 246316 KB Output is correct
3 Correct 87 ms 246316 KB Output is correct
4 Correct 99 ms 246316 KB Output is correct
5 Correct 94 ms 246316 KB Output is correct
6 Correct 104 ms 246316 KB Output is correct
7 Correct 93 ms 246316 KB Output is correct
8 Correct 285 ms 251140 KB Output is correct
9 Correct 323 ms 251140 KB Output is correct
10 Correct 797 ms 262144 KB Output is correct
11 Correct 390 ms 262144 KB Output is correct
12 Correct 407 ms 262144 KB Output is correct
13 Correct 92 ms 262144 KB Output is correct
14 Correct 297 ms 262144 KB Output is correct
15 Correct 138 ms 262144 KB Output is correct
16 Correct 1093 ms 262144 KB Output is correct
17 Correct 414 ms 262144 KB Output is correct
18 Correct 387 ms 262144 KB Output is correct
19 Correct 929 ms 262144 KB Output is correct
20 Correct 891 ms 262144 KB Output is correct
21 Correct 879 ms 262144 KB Output is correct
22 Correct 963 ms 262144 KB Output is correct
23 Correct 875 ms 262144 KB Output is correct
24 Correct 858 ms 262144 KB Output is correct
25 Correct 889 ms 262144 KB Output is correct
26 Correct 892 ms 262144 KB Output is correct
27 Correct 1018 ms 262144 KB Output is correct
28 Correct 877 ms 262144 KB Output is correct
29 Correct 899 ms 262144 KB Output is correct
30 Correct 853 ms 262144 KB Output is correct