Submission #488492

#	Time	Username	Problem	Language	Result	Execution time	Memory
488492		SlavicG	Wall (IOI14_wall)	C++17	0 / 100	11 ms	19064 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].mx >= h)return;
    if(type == 1 && t[i].mn <= 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);
}

int query(int i, int l, int r, int pos){
    push(i, l, r);

    if(l == r)return t[i].mx;
    int mid = l + r >> 1;

    if(pos <= mid){
        return query(2 * i, l, mid, pos);
    }else return query(2 * i + 1, mid + 1, r, pos);

}

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);
    }

    for(int i = 0;i < n; ++ i){
        finalHeight[i] = query(1, 0, n - 1, 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:47:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'int query(int, int, int, int)':
wall.cpp:60:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int mid = l + r >> 1;
      |               ~~^~~

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