oj.uz

Submission #516616

# Submission time Handle Problem Language Result Execution time Memory
516616 2022-01-21T15:37:13 Z status_coding Wall (IOI14_wall) C++14
100 / 100
 601 ms 123980 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

struct segS
{
    pair<int, int> val= {0, 1e9};
    bool lazy = false;
};

vector<segS> seg;

void calc(int p, pair<int, int> val)
{
    if(val.first > seg[p].val.second)
        seg[p].val = {val.first, val.first};

    else if(val.second < seg[p].val.first)
        seg[p].val = {val.second, val.second};

    else
    {
        seg[p].val.first = max(seg[p].val.first, val.first);
        seg[p].val.second = min(seg[p].val.second, val.second);
    }

    seg[p].lazy = true;
}

void push(int p)
{
    if(!seg[p].lazy)
        return;

    calc(2*p, seg[p].val);
    calc(2*p+1, seg[p].val);

    seg[p].val = {0, 1e9};
    seg[p].lazy=false;
}

void upd(int stt, int drt, int st, int dr, int p, pair<int, int> val)
{
    if(stt == st && drt == dr)
    {
        calc(p, val);
        return;
    }

    push(p);

    int mij=(st+dr)/2;

    if(drt <= mij)
        upd(stt, drt, st, mij, 2*p, val);
    else if(stt > mij)
        upd(stt, drt, mij+1, dr, 2*p+1, val);
    else
    {
        upd(stt, mij, st, mij, 2*p, val);
        upd(mij+1, drt, mij+1, dr, 2*p+1, val);
    }
}

void pushAll(int st, int dr, int p, int ans[])
{
    if(st == dr)
    {
        ans[st] = seg[p].val.first;
        return;
    }

    push(p);

    int mij=(st+dr)/2;

    pushAll(st, mij, 2*p, ans);
    pushAll(mij+1, dr, 2*p+1, ans);
}

void afis(int st, int dr, int p)
{
    cout<<st<<' '<<dr<<' '<<seg[p].val.first<<' '<<seg[p].val.second<<' '<<seg[p].lazy<<'\n';

    if(st < dr)
    {
        int mij=(st+dr)/2;
        afis(st, mij, 2*p);
        afis(mij+1, dr, 2*p+1);
    }
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[])
{
    seg.resize(4*n + 4);

    for(int i=0; i<k; i++)
    {
        if(op[i] == 1)
            upd(l[i], r[i], 0, n-1, 1, {h[i], 1e9});
        else
            upd(l[i], r[i], 0, n-1, 1, {0, h[i]});
    }

    pushAll(0, n-1, 1, ans);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 916 KB Output is correct
5 Correct 4 ms 920 KB Output is correct
6 Correct 4 ms 924 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Correct 143 ms 9716 KB Output is correct
3 Correct 145 ms 4816 KB Output is correct
4 Correct 396 ms 16280 KB Output is correct
5 Correct 285 ms 19784 KB Output is correct
6 Correct 207 ms 16744 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 924 KB Output is correct
5 Correct 4 ms 932 KB Output is correct
6 Correct 4 ms 932 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 145 ms 9988 KB Output is correct
9 Correct 149 ms 5392 KB Output is correct
10 Correct 456 ms 16108 KB Output is correct
11 Correct 238 ms 17596 KB Output is correct
12 Correct 210 ms 15864 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 148 ms 9472 KB Output is correct
15 Correct 30 ms 1756 KB Output is correct
16 Correct 526 ms 17160 KB Output is correct
17 Correct 221 ms 17408 KB Output is correct
18 Correct 252 ms 14640 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 912 KB Output is correct
5 Correct 4 ms 920 KB Output is correct
6 Correct 4 ms 916 KB Output is correct
7 Correct 0 ms 292 KB Output is correct
8 Correct 153 ms 9320 KB Output is correct
9 Correct 165 ms 6176 KB Output is correct
10 Correct 463 ms 17312 KB Output is correct
11 Correct 249 ms 16148 KB Output is correct
12 Correct 249 ms 16340 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 213 ms 9452 KB Output is correct
15 Correct 29 ms 1732 KB Output is correct
16 Correct 574 ms 16508 KB Output is correct
17 Correct 238 ms 16040 KB Output is correct
18 Correct 246 ms 14772 KB Output is correct
19 Correct 579 ms 123980 KB Output is correct
20 Correct 601 ms 120348 KB Output is correct
21 Correct 587 ms 123044 KB Output is correct
22 Correct 588 ms 118888 KB Output is correct
23 Correct 560 ms 118724 KB Output is correct
24 Correct 600 ms 120772 KB Output is correct
25 Correct 534 ms 118784 KB Output is correct
26 Correct 598 ms 122364 KB Output is correct
27 Correct 541 ms 121336 KB Output is correct
28 Correct 534 ms 122072 KB Output is correct
29 Correct 528 ms 121472 KB Output is correct
30 Correct 552 ms 122396 KB Output is correct