oj.uz

Submission #93939

# Submission time Handle Problem Language Result Execution time Memory
93939 2019-01-13T16:00:41 Z Alexa2001 Wall (IOI14_wall) C++17
100 / 100
 637 ms 69496 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

using namespace std;

const int lim = 1e5, Nmax = 2e6 + 5;

class SegTree
{
    int a[Nmax<<2], b[Nmax<<2];

    void combine(int node, int x, int y)
    {
        if(b[node] <= x) a[node] = b[node] = x;
            else if(a[node] >= y) a[node] = b[node] = y;
                else a[node] = max(a[node], x), b[node] = min(b[node], y);
    }

    void propag(int node)
    {
        combine(left_son, a[node], b[node]);
        combine(right_son, a[node], b[node]);
        a[node] = 0; b[node] = lim;
    }

public:
    void update(int node, int st, int dr, int L, int R, int A, int B)
    {
        if(L <= st && dr <= R)
        {
            combine(node, A, B);
            return;
        }

        propag(node);

        if(L <= mid) update(left_son, st, mid, L, R, A, B);
        if(mid < R) update(right_son, mid+1, dr, L, R, A, B);
    }

    void propag(int node, int st, int dr, int *Ans)
    {
        if(st == dr)
        {
            Ans[st] = a[node];
            return;
        }
        propag(node);
        propag(left_son, st, mid, Ans);
        propag(right_son, mid+1, dr, Ans);
    }

    void init(int node, int st, int dr)
    {
        a[node] = 0, b[node] = lim;
        if(st == dr) return;
        init(left_son, st, mid); init(right_son, mid+1, dr);
    }
} aint;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    aint.init(1, 0, n-1);
    int i;
    for(i=0; i<k; ++i)
        aint.update(1, 0, n-1, left[i], right[i], (op[i] == 1 ? height[i] : 0), (op[i] == 1 ? lim : height[i]));

    aint.propag(1, 0, n-1, finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 7 ms 892 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 6 ms 764 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 147 ms 14036 KB Output is correct
3 Correct 150 ms 8100 KB Output is correct
4 Correct 426 ms 20344 KB Output is correct
5 Correct 255 ms 21476 KB Output is correct
6 Correct 241 ms 20060 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 7 ms 888 KB Output is correct
5 Correct 5 ms 888 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 140 ms 13916 KB Output is correct
9 Correct 147 ms 8056 KB Output is correct
10 Correct 417 ms 20384 KB Output is correct
11 Correct 248 ms 21496 KB Output is correct
12 Correct 234 ms 19960 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 145 ms 13944 KB Output is correct
15 Correct 31 ms 2040 KB Output is correct
16 Correct 560 ms 20700 KB Output is correct
17 Correct 249 ms 20088 KB Output is correct
18 Correct 250 ms 20088 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 7 ms 764 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 2 ms 372 KB Output is correct
8 Correct 142 ms 13940 KB Output is correct
9 Correct 149 ms 8032 KB Output is correct
10 Correct 428 ms 20472 KB Output is correct
11 Correct 252 ms 21496 KB Output is correct
12 Correct 237 ms 20096 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 146 ms 13944 KB Output is correct
15 Correct 33 ms 2040 KB Output is correct
16 Correct 581 ms 20704 KB Output is correct
17 Correct 255 ms 20088 KB Output is correct
18 Correct 246 ms 20132 KB Output is correct
19 Correct 637 ms 69296 KB Output is correct
20 Correct 566 ms 66932 KB Output is correct
21 Correct 580 ms 69496 KB Output is correct
22 Correct 571 ms 66916 KB Output is correct
23 Correct 585 ms 66936 KB Output is correct
24 Correct 576 ms 66896 KB Output is correct
25 Correct 594 ms 66936 KB Output is correct
26 Correct 571 ms 69344 KB Output is correct
27 Correct 570 ms 69368 KB Output is correct
28 Correct 563 ms 66928 KB Output is correct
29 Correct 564 ms 66944 KB Output is correct
30 Correct 571 ms 66832 KB Output is correct