oj.uz

Submission #1019732

# Submission time Handle Problem Language Result Execution time Memory
1019732 2024-07-11T08:21:16 Z amine_aroua Wall (IOI14_wall) C++17
100 / 100
 719 ms 102484 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
int BASE;
struct Node
{
    int mn , mx;
};
vector<Node> tree , lazy;
void build(int n)
{
    while(__builtin_popcount(BASE) != 1)
        BASE++;
    tree.assign(2*BASE , {(int)1e9  , (int)-1e9});
    lazy.assign(2*BASE , {(int)1e9 , -1});
    for(int i = 0 ; i < n ; i++)
    {
        tree[i + BASE].mx = tree[i + BASE].mn = 0;
    }
    for(int i = BASE - 1 ; i >= 1 ; i--)
    {
        tree[i].mn = min(tree[2*i].mn , tree[2*i + 1].mn);
        tree[i].mx = max(tree[2*i].mx , tree[2*i + 1].mx);
    }
}

void propagate(int node)
{
    if(lazy[node].mn != 1e9)
    {
        for(int i = 2*node ; i <= 2*node + 1 ; i++)
        {
            lazy[i].mn = min(lazy[i].mn , lazy[node].mn);
            lazy[i].mx = min(lazy[i].mx , lazy[node].mn);
            tree[i].mn = min(tree[i].mn , lazy[node].mn);
            tree[i].mx = min(tree[i].mx , lazy[node].mn);
        }
        lazy[node].mn = 1e9;
    }
    if(lazy[node].mx != -1)
    {
        for(int i = 2 * node ; i <= 2*node + 1 ; i++)
        {
            lazy[i].mx = max(lazy[i].mx , lazy[node].mx);
            tree[i].mx = max(tree[i].mx , lazy[node].mx);
            lazy[i].mn = max(lazy[i].mn , lazy[node].mx);
            tree[i].mn = max(tree[i].mn , lazy[node].mx);
        }
        lazy[node].mx = -1;
    }
}
void minimize(int node , int s , int e , int l , int r , int val)
{
    int m = (s + e)/2;
    if(l <= s && e <= r)
    {
        if(tree[node].mx <= val)
            return ;
        if(tree[node].mn >= val)
        {
            tree[node].mx = val;
            lazy[node].mx = val;
            tree[node].mn = val;
            lazy[node].mn = val;
        }
        else
        {
            propagate(node);
            minimize(2*node , s , m , l , r , val);
            minimize(2*node + 1 , m + 1 , e , l , r , val);
            tree[node].mx = max(tree[2*node].mx , tree[2*node + 1].mx);
            tree[node].mn = min(tree[2*node].mn , tree[2*node+ 1].mn);
        }
        return ;
    }
    if(s > r || l > e)
        return ;
    propagate(node);
    minimize(2*node , s , m , l , r , val);
    minimize(2*node + 1 , m + 1 , e , l , r , val);
    tree[node].mx = max(tree[2*node].mx , tree[2*node + 1].mx);
    tree[node].mn = min(tree[2*node].mn , tree[2*node+ 1].mn);
}
void maximize(int node , int s , int e , int l , int r , int val)
{
    int m = (s + e)/2;
    if(l <= s && e <= r)
    {
        if(tree[node].mn >= val)
            return ;
        if(tree[node].mx <= val)
        {
            tree[node].mx = val;
            lazy[node].mx = val;
            tree[node].mn = val;
            lazy[node].mn = val;
        }
        else
        {
            propagate(node);
            maximize(2*node , s , m , l , r , val);
            maximize(2*node + 1 , m + 1 , e , l , r , val);
            tree[node].mx = max(tree[2*node].mx , tree[2*node + 1].mx);
            tree[node].mn = min(tree[2*node].mn , tree[2*node+ 1].mn);
        }
        return ;
    }
    if(s > r || l > e)
        return ;
    propagate(node);
    maximize(2*node , s , m , l , r , val);
    maximize(2*node + 1 , m + 1 , e , l , r , val);
    tree[node].mx = max(tree[2*node].mx , tree[2*node + 1].mx);
    tree[node].mn = min(tree[2*node].mn , tree[2*node+ 1].mn);
}
void maximize(int l , int r , int val)
{
    maximize(1 , 0 , BASE - 1 , l , r , val);
}
void minimize(int l , int r , int val)
{
    minimize(1 , 0 , BASE - 1 , l , r ,val);
}
int query(int node , int s , int e , int i)
{
    if(s == e)
    {
        return tree[node].mn;
    }
    int m = (s + e)/2;
    propagate(node);
    if(s <= i && i <= m)
    {
        return query(2*node , s , m , i);
    }
    else
        return query(2*node + 1, m + 1 , e , i);
}
int query(int i)
{
    return query(1 , 0 , BASE - 1 , i);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    BASE = n;
    build(n);
    for(int i = 0 ; i < k ; i++)
    {
        if(op[i] == 1)
        {
            maximize(left[i] , right[i] , height[i]);
        }
        else
        {
            minimize(left[i] , right[i] , height[i]);
        }
    }
    for(int i = 0 ; i < n ; i++)
    {
        finalHeight[i] = query(i);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 572 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1216 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 85 ms 13900 KB Output is correct
3 Correct 112 ms 8524 KB Output is correct
4 Correct 363 ms 22380 KB Output is correct
5 Correct 235 ms 23376 KB Output is correct
6 Correct 206 ms 21844 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 1164 KB Output is correct
6 Correct 4 ms 1144 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 91 ms 13904 KB Output is correct
9 Correct 125 ms 8532 KB Output is correct
10 Correct 345 ms 22356 KB Output is correct
11 Correct 217 ms 23376 KB Output is correct
12 Correct 208 ms 21840 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 90 ms 13908 KB Output is correct
15 Correct 30 ms 2528 KB Output is correct
16 Correct 579 ms 22748 KB Output is correct
17 Correct 221 ms 22100 KB Output is correct
18 Correct 220 ms 22148 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 1200 KB Output is correct
6 Correct 4 ms 1144 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 85 ms 13880 KB Output is correct
9 Correct 127 ms 8784 KB Output is correct
10 Correct 344 ms 22356 KB Output is correct
11 Correct 206 ms 23376 KB Output is correct
12 Correct 214 ms 21920 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 91 ms 13908 KB Output is correct
15 Correct 29 ms 2644 KB Output is correct
16 Correct 584 ms 22592 KB Output is correct
17 Correct 221 ms 22124 KB Output is correct
18 Correct 222 ms 22168 KB Output is correct
19 Correct 659 ms 102240 KB Output is correct
20 Correct 719 ms 99940 KB Output is correct
21 Correct 683 ms 102248 KB Output is correct
22 Correct 670 ms 99912 KB Output is correct
23 Correct 694 ms 99844 KB Output is correct
24 Correct 713 ms 99920 KB Output is correct
25 Correct 687 ms 99728 KB Output is correct
26 Correct 681 ms 102292 KB Output is correct
27 Correct 683 ms 102484 KB Output is correct
28 Correct 655 ms 99768 KB Output is correct
29 Correct 680 ms 99920 KB Output is correct
30 Correct 696 ms 99780 KB Output is correct