oj.uz

Submission #1016596

# Submission time Handle Problem Language Result Execution time Memory
1016596 2024-07-08T08:41:32 Z Ice_man Wall (IOI14_wall) C++14
100 / 100
 507 ms 140112 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include "wall.h"

#define maxn 2000005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

using namespace std;


typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef long double ld;


std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}



int lazy[maxn * 4];
pii tree[maxn * 4];


void push_lazy(int node, int l, int r)
{
    if(lazy[node] == -1)
        return;

    tree[node].X = lazy[node];
    tree[node].Y = lazy[node];

    if(l != r)
    {
        lazy[node * 2] = lazy[node];
        lazy[node * 2 + 1] = lazy[node];
    }

    lazy[node] = -1;
}


void _remove(int node, int l, int r, int ql, int qr, int qval)
{
    push_lazy(node, l, r);
    if(ql > r || qr < l)
        return;

    if(tree[node].Y <= qval)
        return;

    if(l >= ql && r <= qr && tree[node].X >= qval)
    {
        lazy[node] = qval;
        push_lazy(node, l, r);
        return;
    }

    int mid = (l + r) / 2;

    _remove(node * 2, l, mid, ql, qr, qval);
    _remove(node * 2 + 1, mid + 1, r, ql, qr, qval);

    tree[node].Y = max(tree[node * 2].Y , tree[node * 2 + 1].Y);
    tree[node].X = min(tree[node * 2].X , tree[node * 2 + 1].X);
}



void add(int node, int l, int r, int ql, int qr, int qval)
{
    push_lazy(node, l, r);
    if(ql > r || qr < l)
        return;

    if(tree[node].X >= qval)
        return;

    if(l >= ql && r <= qr && tree[node].Y <= qval)
    {
        lazy[node] = qval;
        push_lazy(node, l, r);
        return;
    }

    int mid = (l + r) / 2;

    add(node * 2, l, mid, ql, qr, qval);
    add(node * 2 + 1, mid + 1, r, ql, qr, qval);

    tree[node].Y = max(tree[node * 2].Y , tree[node * 2 + 1].Y);
    tree[node].X = min(tree[node * 2].X , tree[node * 2 + 1].X);
}


int ans[maxn];
void answer(int node , int l , int r)
{
    push_lazy(node , l , r);

    if(l == r)
    {
        ans[l - 1] = tree[node].X;
        return;
    }

    int mid = (l + r) / 2;

    answer(node * 2 , l , mid);
    answer(node * 2 + 1 , mid + 1 , r);
}


int pom[maxn];
void buildWall(int n , int k , int op[] , int left[] , int right[] , int height[] , int finalHeight[])
{
    n++;
    for(int i = 0; i < 4 * maxn; i++)
        lazy[i] = -1 , tree[i] = {0 , 0};

    for(int i = 0; i < k; i++)
        if(op[i] == 1)
            add(1 , 1 , n , left[i] + 1 , right[i] + 1 , height[i]);
        else
            _remove(1 , 1 , n , left[i] + 1 , right[i] + 1 , height[i]);

    answer(1 , 1 , n);
    for(int i = 0; i < n - 1; i++)
        finalHeight[i] = ans[i];
}





/**int main()
{

#ifdef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ///startT = std::chrono::high_resolution_clock::now();

    add(1 , 1 , 10 , 2 , 9 , 4);
    _remove(1 , 1 , 10 , 5 , 10 , 1);
    _remove(1 , 1 , 10 , 4 , 7 , 5);
    add(1 , 1 , 10 , 1 , 6 , 3);
    add(1 , 1 , 10 , 3 , 3 , 5);
    _remove(1 , 1 , 10 , 7 , 8 , 0);

    answer(1 , 1 , 10);
    for(int i = 0; i < 10; i++)
        cout << ans[i] << " ";
    cout << endl;



    return 0;
}
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 95324 KB Output is correct
2 Correct 21 ms 95464 KB Output is correct
3 Correct 21 ms 95320 KB Output is correct
4 Correct 23 ms 95500 KB Output is correct
5 Correct 22 ms 95580 KB Output is correct
6 Correct 25 ms 95428 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 95324 KB Output is correct
2 Correct 100 ms 103320 KB Output is correct
3 Correct 70 ms 98896 KB Output is correct
4 Correct 127 ms 104276 KB Output is correct
5 Correct 129 ms 104788 KB Output is correct
6 Correct 146 ms 104672 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 95324 KB Output is correct
2 Correct 21 ms 95320 KB Output is correct
3 Correct 21 ms 95324 KB Output is correct
4 Correct 23 ms 95656 KB Output is correct
5 Correct 23 ms 95580 KB Output is correct
6 Correct 21 ms 95580 KB Output is correct
7 Correct 18 ms 95320 KB Output is correct
8 Correct 101 ms 103252 KB Output is correct
9 Correct 68 ms 98896 KB Output is correct
10 Correct 133 ms 104272 KB Output is correct
11 Correct 129 ms 104764 KB Output is correct
12 Correct 153 ms 104788 KB Output is correct
13 Correct 20 ms 95324 KB Output is correct
14 Correct 106 ms 103256 KB Output is correct
15 Correct 39 ms 96080 KB Output is correct
16 Correct 333 ms 113940 KB Output is correct
17 Correct 221 ms 113488 KB Output is correct
18 Correct 238 ms 113492 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 95324 KB Output is correct
2 Correct 19 ms 95324 KB Output is correct
3 Correct 20 ms 95324 KB Output is correct
4 Correct 22 ms 95576 KB Output is correct
5 Correct 22 ms 95644 KB Output is correct
6 Correct 25 ms 95576 KB Output is correct
7 Correct 19 ms 95464 KB Output is correct
8 Correct 109 ms 103088 KB Output is correct
9 Correct 68 ms 98896 KB Output is correct
10 Correct 128 ms 104276 KB Output is correct
11 Correct 140 ms 104784 KB Output is correct
12 Correct 156 ms 104736 KB Output is correct
13 Correct 19 ms 95312 KB Output is correct
14 Correct 107 ms 103240 KB Output is correct
15 Correct 42 ms 95968 KB Output is correct
16 Correct 341 ms 113968 KB Output is correct
17 Correct 218 ms 113388 KB Output is correct
18 Correct 220 ms 113492 KB Output is correct
19 Correct 484 ms 138576 KB Output is correct
20 Correct 467 ms 136104 KB Output is correct
21 Correct 507 ms 138604 KB Output is correct
22 Correct 480 ms 136204 KB Output is correct
23 Correct 472 ms 135920 KB Output is correct
24 Correct 493 ms 136016 KB Output is correct
25 Correct 497 ms 136016 KB Output is correct
26 Correct 483 ms 138604 KB Output is correct
27 Correct 478 ms 140112 KB Output is correct
28 Correct 477 ms 135872 KB Output is correct
29 Correct 484 ms 136020 KB Output is correct
30 Correct 493 ms 136020 KB Output is correct