oj.uz

Submission #1016888

# Submission time Handle Problem Language Result Execution time Memory
1016888 2024-07-08T14:36:27 Z Ice_man Wall (IOI14_wall) C++14
100 / 100
 551 ms 128160 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].Y;
        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 16 ms 95324 KB Output is correct
2 Correct 18 ms 95528 KB Output is correct
3 Correct 17 ms 95324 KB Output is correct
4 Correct 19 ms 95492 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 16 ms 95324 KB Output is correct
2 Correct 99 ms 103100 KB Output is correct
3 Correct 65 ms 98844 KB Output is correct
4 Correct 125 ms 104208 KB Output is correct
5 Correct 134 ms 104572 KB Output is correct
6 Correct 142 ms 104784 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 95320 KB Output is correct
2 Correct 17 ms 95576 KB Output is correct
3 Correct 18 ms 95392 KB Output is correct
4 Correct 20 ms 95580 KB Output is correct
5 Correct 20 ms 95572 KB Output is correct
6 Correct 21 ms 95576 KB Output is correct
7 Correct 17 ms 95324 KB Output is correct
8 Correct 97 ms 103304 KB Output is correct
9 Correct 65 ms 98896 KB Output is correct
10 Correct 124 ms 104272 KB Output is correct
11 Correct 134 ms 104548 KB Output is correct
12 Correct 141 ms 104784 KB Output is correct
13 Correct 16 ms 95396 KB Output is correct
14 Correct 117 ms 103248 KB Output is correct
15 Correct 34 ms 96084 KB Output is correct
16 Correct 327 ms 104448 KB Output is correct
17 Correct 210 ms 104332 KB Output is correct
18 Correct 222 ms 104528 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 95324 KB Output is correct
2 Correct 18 ms 95580 KB Output is correct
3 Correct 16 ms 95420 KB Output is correct
4 Correct 20 ms 95580 KB Output is correct
5 Correct 19 ms 95592 KB Output is correct
6 Correct 19 ms 95580 KB Output is correct
7 Correct 16 ms 95320 KB Output is correct
8 Correct 98 ms 103208 KB Output is correct
9 Correct 65 ms 98900 KB Output is correct
10 Correct 127 ms 104296 KB Output is correct
11 Correct 135 ms 104788 KB Output is correct
12 Correct 140 ms 104620 KB Output is correct
13 Correct 17 ms 95324 KB Output is correct
14 Correct 112 ms 103160 KB Output is correct
15 Correct 33 ms 96084 KB Output is correct
16 Correct 343 ms 104336 KB Output is correct
17 Correct 213 ms 104532 KB Output is correct
18 Correct 216 ms 104528 KB Output is correct
19 Correct 479 ms 128080 KB Output is correct
20 Correct 472 ms 125524 KB Output is correct
21 Correct 472 ms 128068 KB Output is correct
22 Correct 468 ms 125520 KB Output is correct
23 Correct 500 ms 125500 KB Output is correct
24 Correct 467 ms 125588 KB Output is correct
25 Correct 469 ms 125588 KB Output is correct
26 Correct 511 ms 128136 KB Output is correct
27 Correct 551 ms 128160 KB Output is correct
28 Correct 458 ms 125592 KB Output is correct
29 Correct 513 ms 125584 KB Output is correct
30 Correct 467 ms 127124 KB Output is correct