oj.uz

Submission #1016887

# Submission time Handle Problem Language Result Execution time Memory
1016887 2024-07-08T14:36:05 Z Ice_man Wall (IOI14_wall) C++14
100 / 100
 502 ms 138580 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 17 ms 95324 KB Output is correct
2 Correct 17 ms 95580 KB Output is correct
3 Correct 17 ms 95516 KB Output is correct
4 Correct 20 ms 95576 KB Output is correct
5 Correct 19 ms 95580 KB Output is correct
6 Correct 19 ms 95580 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 95320 KB Output is correct
2 Correct 107 ms 109064 KB Output is correct
3 Correct 66 ms 102704 KB Output is correct
4 Correct 131 ms 113740 KB Output is correct
5 Correct 136 ms 114892 KB Output is correct
6 Correct 145 ms 113232 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 95324 KB Output is correct
2 Correct 16 ms 95580 KB Output is correct
3 Correct 18 ms 95328 KB Output is correct
4 Correct 20 ms 95580 KB Output is correct
5 Correct 21 ms 95568 KB Output is correct
6 Correct 18 ms 95772 KB Output is correct
7 Correct 17 ms 95324 KB Output is correct
8 Correct 100 ms 108920 KB Output is correct
9 Correct 65 ms 102676 KB Output is correct
10 Correct 132 ms 113744 KB Output is correct
11 Correct 129 ms 114768 KB Output is correct
12 Correct 145 ms 113384 KB Output is correct
13 Correct 18 ms 95324 KB Output is correct
14 Correct 110 ms 109100 KB Output is correct
15 Correct 35 ms 96596 KB Output is correct
16 Correct 327 ms 114124 KB Output is correct
17 Correct 214 ms 113436 KB Output is correct
18 Correct 227 ms 113492 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 95320 KB Output is correct
2 Correct 17 ms 95576 KB Output is correct
3 Correct 17 ms 95320 KB Output is correct
4 Correct 20 ms 95580 KB Output is correct
5 Correct 19 ms 95764 KB Output is correct
6 Correct 20 ms 95580 KB Output is correct
7 Correct 16 ms 95320 KB Output is correct
8 Correct 100 ms 108972 KB Output is correct
9 Correct 65 ms 102480 KB Output is correct
10 Correct 127 ms 113744 KB Output is correct
11 Correct 129 ms 114940 KB Output is correct
12 Correct 143 ms 113236 KB Output is correct
13 Correct 16 ms 95436 KB Output is correct
14 Correct 102 ms 108892 KB Output is correct
15 Correct 34 ms 96596 KB Output is correct
16 Correct 326 ms 113968 KB Output is correct
17 Correct 229 ms 113488 KB Output is correct
18 Correct 226 ms 113456 KB Output is correct
19 Correct 449 ms 138412 KB Output is correct
20 Correct 431 ms 136020 KB Output is correct
21 Correct 471 ms 138392 KB Output is correct
22 Correct 479 ms 136020 KB Output is correct
23 Correct 502 ms 136020 KB Output is correct
24 Correct 468 ms 135932 KB Output is correct
25 Correct 471 ms 135956 KB Output is correct
26 Correct 471 ms 138576 KB Output is correct
27 Correct 464 ms 138580 KB Output is correct
28 Correct 458 ms 136016 KB Output is correct
29 Correct 469 ms 136032 KB Output is correct
30 Correct 465 ms 136104 KB Output is correct