oj.uz

Submission #380830

# Submission time Handle Problem Language Result Execution time Memory
380830 2021-03-23T08:37:28 Z IloveN Wall (IOI14_wall) C++14
100 / 100
 809 ms 171628 KB 
#include<bits/stdc++.h>
#include "wall.h"

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=2e6+10;

struct segment_tree
{
    pii it[N * 4];
    int Size;

    pii combine(pii obj, pii range)
    {
        obj.fi = max(obj.fi, range.fi);
        obj.se = max(obj.se, range.fi);
        obj.fi = min(obj.fi, range.se);
        obj.se = min(obj.se, range.se);
        return obj;
    }

    void build(int id, int l, int r)
    {
        if (l == r)
        {
            it[id] = mp(0,1e5);
            return;
        }
        int mid = (l+r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        it[id] = combine(it[id * 2], it[id * 2 + 1]);
    }

    void update(int id, int l, int r, int pos, pii range)
    {
        if (l == r)
        {
            it[id] = range;
            return;
        }
        int mid = (l+r) / 2;
        if (pos <= mid) update(id * 2, l, mid, pos, range);
        else update(id * 2 + 1, mid + 1, r, pos, range);
        it[id] = combine(it[id * 2], it[id * 2 + 1]);
    }

    void change(int pos, pii range) { update(1, 1, Size, pos, range);}
    int get() { return it[1].fi;}
} seg;

struct event
{
    int id;
    pii range;
};

vector<event> vt[N];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < k; ++i)
    {
        pii range = mp(0,1e5);
        if (op[i] == 1) range.fi = height[i];
        else range.se = height[i];
        vt[left[i]].pb({i + 1, range});
        vt[right[i] + 1].pb({i + 1, mp(0,1e5)});
    }
    seg.Size = k;
    seg.build(1, 1, k);
    for (int i = 0; i < n; ++i)
    {
        for (event e : vt[i]) seg.change(e.id, e.range);
        finalHeight[i] = seg.get();
    }
    return;
}


/*int main()
{
    //freopen("ss.inp","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 109932 KB Output is correct
2 Correct 70 ms 110316 KB Output is correct
3 Correct 68 ms 110060 KB Output is correct
4 Correct 73 ms 110444 KB Output is correct
5 Correct 71 ms 110444 KB Output is correct
6 Correct 71 ms 110444 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 109932 KB Output is correct
2 Correct 337 ms 135608 KB Output is correct
3 Correct 300 ms 124908 KB Output is correct
4 Correct 770 ms 147948 KB Output is correct
5 Correct 490 ms 146124 KB Output is correct
6 Correct 466 ms 143852 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 110076 KB Output is correct
2 Correct 71 ms 110316 KB Output is correct
3 Correct 70 ms 110188 KB Output is correct
4 Correct 75 ms 110444 KB Output is correct
5 Correct 72 ms 110444 KB Output is correct
6 Correct 72 ms 110444 KB Output is correct
7 Correct 68 ms 109932 KB Output is correct
8 Correct 338 ms 135524 KB Output is correct
9 Correct 292 ms 124780 KB Output is correct
10 Correct 795 ms 147948 KB Output is correct
11 Correct 543 ms 146316 KB Output is correct
12 Correct 494 ms 143852 KB Output is correct
13 Correct 67 ms 109932 KB Output is correct
14 Correct 336 ms 135608 KB Output is correct
15 Correct 101 ms 112492 KB Output is correct
16 Correct 763 ms 148204 KB Output is correct
17 Correct 461 ms 143980 KB Output is correct
18 Correct 480 ms 143524 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 109932 KB Output is correct
2 Correct 70 ms 110316 KB Output is correct
3 Correct 69 ms 110060 KB Output is correct
4 Correct 73 ms 110444 KB Output is correct
5 Correct 75 ms 110416 KB Output is correct
6 Correct 71 ms 110444 KB Output is correct
7 Correct 67 ms 109932 KB Output is correct
8 Correct 337 ms 135492 KB Output is correct
9 Correct 295 ms 124780 KB Output is correct
10 Correct 786 ms 147844 KB Output is correct
11 Correct 470 ms 146284 KB Output is correct
12 Correct 457 ms 143852 KB Output is correct
13 Correct 68 ms 109932 KB Output is correct
14 Correct 346 ms 135492 KB Output is correct
15 Correct 97 ms 112364 KB Output is correct
16 Correct 809 ms 148076 KB Output is correct
17 Correct 471 ms 144108 KB Output is correct
18 Correct 460 ms 143596 KB Output is correct
19 Correct 801 ms 171492 KB Output is correct
20 Correct 737 ms 168940 KB Output is correct
21 Correct 808 ms 171468 KB Output is correct
22 Correct 759 ms 169008 KB Output is correct
23 Correct 751 ms 169028 KB Output is correct
24 Correct 756 ms 168888 KB Output is correct
25 Correct 794 ms 168812 KB Output is correct
26 Correct 762 ms 171628 KB Output is correct
27 Correct 754 ms 171332 KB Output is correct
28 Correct 739 ms 169084 KB Output is correct
29 Correct 742 ms 169068 KB Output is correct
30 Correct 769 ms 168940 KB Output is correct