oj.uz

Submission #289157

# Submission time Handle Problem Language Result Execution time Memory
289157 2020-09-02T12:18:06 Z stoyan_malinin Wall (IOI14_wall) C++14
100 / 100
 1527 ms 201336 KB 
#include "wall.h"
//#include "grader.cpp"

#include <vector>
#include <iostream>

using namespace std;

const int MAXN = 2e6 + 5;

struct Range
{
    int l, r;

    Range(){}
    Range(int l, int r)
    {
        this->l = l;
        this->r = r;
    }

    int f(int x)
    {
        if(x<=l) return l;
        if(x>=r) return r;
        return x;
    }
};

Range Merge(Range first, Range second)
{
    if(second.l>=first.r) return Range(second.l, second.l);
    if(second.r<=first.l) return Range(second.r, second.r);
    if(second.l<=first.l && first.r<=second.r) return Range(first.l, first.r);
    if(first.l<=second.l && second.r<=first.r) return Range(second.l, second.r);
    if(first.l<=second.l && first.r<=second.r && second.l<=first.r) return Range(second.l, first.r);
    if(second.l<=first.l && second.r<=first.r && first.l<=second.r) return Range(first.l, second.r);
}

struct SegmentTree
{
    Range val;

    int l, r;
    SegmentTree *L, *R;

    SegmentTree(){}
    SegmentTree(int l, int r)
    {
        this->val = Range(0, MAXN);
        this->l = l;
        this->r = r;

        this->L = nullptr;
        this->R = nullptr;
    }

    void build()
    {
        if(l==r) return;

        L = new SegmentTree(l, (l+r)/2);
        R = new SegmentTree((l+r)/2+1, r);

        L->build();
        R->build();
    }

    void rem(int q)
    {
        if(l==r && q==l)
        {
            val = Range(0, MAXN);
            return;
        }
        if(q<l || q>r) return;

        L->rem(q);
        R->rem(q);
        val = Merge(L->val, R->val);
    }

    void add(int q, Range newVal)
    {
        if(l==r && q==l)
        {
            val = newVal;
            return;
        }
        if(q<l || q>r) return;

        L->add(q, newVal);
        R->add(q, newVal);
        val = Merge(L->val, R->val);
    }

    void reset()
    {
        //if(val==Range(0, MAXN)) return;
        val = Range(0, MAXN);

        if(L!=nullptr)
        {
            L->reset();
            R->reset();
        }
    }
};

vector <int> toRemove[MAXN], toAdd[MAXN];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    SegmentTree *T = new SegmentTree(0, k-1);
    T->build();

    for(int i = 0;i<k;i++)
    {
        toAdd[ left[i] ].push_back(i);
        toRemove[ right[i] ].push_back(i);
    }

    for(int ind = 0;ind<n;ind++)
    {
        if(ind!=0)
        {
            for(int i: toRemove[ind-1])
                T->rem(i);
        }

        for(int i: toAdd[ind])
        {
            if(op[i]==1) T->add(i, Range(height[i], MAXN));//ans = Merge(ans, Range(height[i], MAXN));
            else T->add(i, Range(0, height[i]));//ans = Merge(ans, Range(0, height[i]));
        }

        finalHeight[ind] = T->val.f(0);
    }
}

Compilation message

wall.cpp: In function 'Range Merge(Range, Range)':
wall.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 94200 KB Output is correct
2 Correct 60 ms 94840 KB Output is correct
3 Correct 58 ms 94456 KB Output is correct
4 Correct 65 ms 95100 KB Output is correct
5 Correct 74 ms 95096 KB Output is correct
6 Correct 63 ms 95096 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94200 KB Output is correct
2 Correct 404 ms 153228 KB Output is correct
3 Correct 501 ms 120440 KB Output is correct
4 Correct 1527 ms 159232 KB Output is correct
5 Correct 609 ms 157432 KB Output is correct
6 Correct 589 ms 157048 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94200 KB Output is correct
2 Correct 67 ms 94840 KB Output is correct
3 Correct 65 ms 94548 KB Output is correct
4 Correct 72 ms 95096 KB Output is correct
5 Correct 69 ms 95096 KB Output is correct
6 Correct 69 ms 95096 KB Output is correct
7 Correct 64 ms 94200 KB Output is correct
8 Correct 411 ms 153224 KB Output is correct
9 Correct 508 ms 120568 KB Output is correct
10 Correct 1443 ms 159224 KB Output is correct
11 Correct 597 ms 157560 KB Output is correct
12 Correct 584 ms 157052 KB Output is correct
13 Correct 63 ms 94200 KB Output is correct
14 Correct 411 ms 153100 KB Output is correct
15 Correct 113 ms 98552 KB Output is correct
16 Correct 1439 ms 159388 KB Output is correct
17 Correct 617 ms 156920 KB Output is correct
18 Correct 617 ms 156664 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 94200 KB Output is correct
2 Correct 66 ms 94840 KB Output is correct
3 Correct 65 ms 94444 KB Output is correct
4 Correct 72 ms 95096 KB Output is correct
5 Correct 70 ms 95096 KB Output is correct
6 Correct 71 ms 95096 KB Output is correct
7 Correct 64 ms 94324 KB Output is correct
8 Correct 411 ms 153224 KB Output is correct
9 Correct 518 ms 120448 KB Output is correct
10 Correct 1450 ms 159244 KB Output is correct
11 Correct 614 ms 157432 KB Output is correct
12 Correct 582 ms 157152 KB Output is correct
13 Correct 66 ms 94200 KB Output is correct
14 Correct 419 ms 153100 KB Output is correct
15 Correct 114 ms 98680 KB Output is correct
16 Correct 1470 ms 159468 KB Output is correct
17 Correct 626 ms 156792 KB Output is correct
18 Correct 619 ms 156536 KB Output is correct
19 Correct 868 ms 190840 KB Output is correct
20 Correct 860 ms 198820 KB Output is correct
21 Correct 877 ms 201208 KB Output is correct
22 Correct 867 ms 198904 KB Output is correct
23 Correct 876 ms 198808 KB Output is correct
24 Correct 856 ms 198648 KB Output is correct
25 Correct 853 ms 198648 KB Output is correct
26 Correct 941 ms 201336 KB Output is correct
27 Correct 867 ms 201208 KB Output is correct
28 Correct 875 ms 198780 KB Output is correct
29 Correct 851 ms 198648 KB Output is correct
30 Correct 854 ms 198776 KB Output is correct