oj.uz

Submission #488504

# Submission time Handle Problem Language Result Execution time Memory
488504 2021-11-19T10:57:21 Z SlavicG Wall (IOI14_wall) C++17
100 / 100
 765 ms 240216 KB 
#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 2e6 + 10;
struct node{
    ll mx;
    ll mn;
    int lazy;
};

node t[4 * N];

void push(int i, int l, int r){
    if(t[i].lazy == -1)return;

    t[i].mx = t[i].mn = t[i].lazy;

    if(l != r){
        t[2 * i].lazy = t[i].lazy;
        t[2 * i + 1].lazy = t[i].lazy;
    }
    t[i].lazy = -1;
}

void modif(int i, int l, int r, int tl, int tr, int h, int type){
    push(i, l, r);
    if(l > tr || r < tl)return;

    if(type == 0 && t[i].mn >= h)return;
    if(type == 1 && t[i].mx <= h)return;

    if(type == 0){
        if(l >= tl && r <= tr && t[i].mx <= h){
            t[i].lazy = h;
            push(i, l, r);
            return;
        }
    }

    if(type == 1){
        if(l >= tl && r <= tr && t[i].mn >= h){
            t[i].lazy = h;
            push(i, l, r);
            return;
        }
    }

    int mid = l + r >> 1;

    modif(2 * i, l, mid, tl, tr, h, type);
    modif(2 * i + 1, mid + 1, r, tl, tr, h, type);

    t[i].mx = max(t[2 * i].mx, t[2 * i + 1].mx);
    t[i].mn = min(t[2 * i].mn, t[2 * i + 1].mn);
}


ll ans[N];
void build(int i, int l, int r){
    push(i, l, r);
    if(l == r){
        ans[l] = t[i].mx;
        return;
    }
    int mid = l + r >> 1;
    build(2 * i, l, mid);
    build(2 * i + 1, mid + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i = 0;i < 4 * N; ++i){
        t[i].lazy = -1;
        t[i].mn = t[i].mx = 0;
    }

    for(int i = 0;i < k; ++i){
        int type = op[i], l = left[i], r = right[i], h = height[i];
        --type;
        modif(1, 0, n - 1, l, r, h, type);
    }

    build(1, 0, n - 1);

     for(int i = 0;i < n; ++ i){
        finalHeight[i] = ans[i];
    }

    return;
}

/*
void solve()
{ 

}   
 
int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}

*/

Compilation message

wall.cpp: In function 'void modif(int, int, int, int, int, int, int)':
wall.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'void build(int, int, int)':
wall.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 188136 KB Output is correct
2 Correct 81 ms 188116 KB Output is correct
3 Correct 78 ms 188140 KB Output is correct
4 Correct 86 ms 188400 KB Output is correct
5 Correct 80 ms 188288 KB Output is correct
6 Correct 81 ms 188292 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 188112 KB Output is correct
2 Correct 208 ms 195920 KB Output is correct
3 Correct 144 ms 191640 KB Output is correct
4 Correct 230 ms 197316 KB Output is correct
5 Correct 245 ms 197924 KB Output is correct
6 Correct 266 ms 197836 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 188076 KB Output is correct
2 Correct 78 ms 188220 KB Output is correct
3 Correct 78 ms 188100 KB Output is correct
4 Correct 83 ms 188360 KB Output is correct
5 Correct 89 ms 188364 KB Output is correct
6 Correct 80 ms 188304 KB Output is correct
7 Correct 77 ms 188148 KB Output is correct
8 Correct 204 ms 196020 KB Output is correct
9 Correct 148 ms 191684 KB Output is correct
10 Correct 228 ms 197288 KB Output is correct
11 Correct 242 ms 197876 KB Output is correct
12 Correct 271 ms 197832 KB Output is correct
13 Correct 79 ms 188144 KB Output is correct
14 Correct 217 ms 196008 KB Output is correct
15 Correct 102 ms 188900 KB Output is correct
16 Correct 578 ms 197572 KB Output is correct
17 Correct 367 ms 197576 KB Output is correct
18 Correct 372 ms 197612 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 188188 KB Output is correct
2 Correct 79 ms 188180 KB Output is correct
3 Correct 78 ms 188184 KB Output is correct
4 Correct 81 ms 188360 KB Output is correct
5 Correct 82 ms 188356 KB Output is correct
6 Correct 80 ms 188384 KB Output is correct
7 Correct 76 ms 188072 KB Output is correct
8 Correct 201 ms 195908 KB Output is correct
9 Correct 144 ms 191600 KB Output is correct
10 Correct 244 ms 197316 KB Output is correct
11 Correct 245 ms 197864 KB Output is correct
12 Correct 263 ms 197828 KB Output is correct
13 Correct 79 ms 188088 KB Output is correct
14 Correct 213 ms 195992 KB Output is correct
15 Correct 101 ms 188824 KB Output is correct
16 Correct 527 ms 197540 KB Output is correct
17 Correct 361 ms 197700 KB Output is correct
18 Correct 357 ms 197600 KB Output is correct
19 Correct 759 ms 229924 KB Output is correct
20 Correct 752 ms 237656 KB Output is correct
21 Correct 765 ms 240216 KB Output is correct
22 Correct 758 ms 237752 KB Output is correct
23 Correct 758 ms 237736 KB Output is correct
24 Correct 751 ms 237692 KB Output is correct
25 Correct 752 ms 237660 KB Output is correct
26 Correct 764 ms 240196 KB Output is correct
27 Correct 758 ms 240124 KB Output is correct
28 Correct 740 ms 237660 KB Output is correct
29 Correct 753 ms 237748 KB Output is correct
30 Correct 760 ms 237704 KB Output is correct