Submission #1026890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026890		khanhtb	Wall (IOI14_wall)	C++14	100 / 100	521 ms	237908 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
const ll blocksz = 320;
const ll N = 2e6 + 8;
ll ans[N];
struct Segment_Tree{
    vpll st;
    vi lz;
    void init(ll n){
        st = vpll(n<<2);
        lz = vi(n<<2,-1);
    }
    void update_node(ll id, ll x){
        st[id].fi = st[id].se = x;
        lz[id] = x;
    }
    void push(ll id){
        if(lz[id] == -1) return;
        update_node(id<<1,lz[id]);
        update_node(id<<1|1,lz[id]);
        lz[id] = -1;
    }
    void update(ll id, ll l, ll r, ll u, ll v, ll x, bool type){
        if(v < l || r < u) return;
        if(!type && st[id].fi >= x) return;
        if(type && st[id].se <= x) return;
        if(u <= l && r <= v){
            if(!type && st[id].se <= x){
                update_node(id,x);
                return;
            }
            if(type && st[id].fi >= x){
                update_node(id,x);
                return;
            }
        }
        push(id);
        ll m = l+r>>1;
        update(id<<1,l,m,u,v,x,type);
        update(id<<1|1,m+1,r,u,v,x,type);
        st[id].fi = min(st[id<<1].fi,st[id<<1|1].fi);
        st[id].se = max(st[id<<1].se, st[id<<1|1].se);
    }
    void get(ll id, ll l, ll r){
        if(l == r){
            ans[l] = st[id].se;
            return;
        }
        push(id);
        ll m = l+r>>1;
        get(id<<1,l,m);
        get(id<<1|1,m+1,r);
    }
} st;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    st.init(n);
    for(ll i = 0; i < k; i++){
        left[i]++,right[i]++;
        if(op[i] == 1) st.update(1,1,n,left[i],right[i],height[i],0);
        if(op[i] == 2) st.update(1,1,n,left[i],right[i],height[i],1);
    }
    st.get(1,1,n);
    for(ll i = 0; i < n; i++) finalHeight[i] = ans[i+1];
}

Compilation message (stderr)

wall.cpp: In member function 'void Segment_Tree::update(long long int, long long int, long long int, long long int, long long int, long long int, bool)':
wall.cpp:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         ll m = l+r>>1;
      |                ~^~
wall.cpp: In member function 'void Segment_Tree::get(long long int, long long int, long long int)':
wall.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         ll m = l+r>>1;
      |                ~^~

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