Submission #488497

#	Time	Username	Problem	Language	Result	Execution time	Memory
488497		SlavicG	Wall (IOI14_wall)	C++17	0 / 100	131 ms	26852 KiB

wall

#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 = 2e5 + 10;
struct node{
    ll mx;
    ll mn;
    ll 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[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(l >= tl && r <= tr){
        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 (stderr)

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

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39