Submission #412549

#	Time	Username	Problem	Language	Result	Execution time	Memory
412549		Karliver	Wall (IOI14_wall)	C++14	100 / 100	897 ms	107344 KiB

wall

#include "wall.h"
    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int N = 2e6 + 10;
const double eps = 1e-7;

template <class T> using V = vector<T>;  // from yosupo 
template <class T> using VV = V<V<T>>;  // from yosupo

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}

struct node{
    int up = 0, down = INF;
    node(){}
} d[4*N];
void apply(int ind, int up, int down){
    if(ind>=0&&ind<4*N){
        d[ind].down = min(d[ind].down,down);
        d[ind].down = max(d[ind].down,up);
        d[ind].up = max(d[ind].up,up);
        d[ind].up = min(d[ind].up,down);
    }
}
void range_modify(int mode, int ml, int mr, int val, int ind = 1, int l = 0, int r = N-1){
    if(ml>r||mr<l) return;
    if(ml<=l&&mr>=r){
        if(mode){
            d[ind].down = min(d[ind].down,val);
            d[ind].up = min(d[ind].up,val);
        }
        else{
            d[ind].down = max(d[ind].down,val);
            d[ind].up = max(d[ind].up,val);
        }
        return;
    }
    int mid = (l+r)/2;
    apply(ind<<1,d[ind].up,d[ind].down);
    apply(ind<<1|1,d[ind].up,d[ind].down);
    d[ind].up = 0, d[ind].down = INF;
    range_modify(mode,ml,mr,val,ind<<1,l,mid);
    range_modify(mode,ml,mr,val,ind<<1|1,mid+1,r);
}
int n,k;
V<int> ans(n);
void query(int ind, int l, int r){
    if(l==r){
        if(l!=n) ans.push_back(min(d[ind].up,d[ind].down));
        return;
    }
    apply(ind<<1,d[ind].up,d[ind].down);
    apply(ind<<1|1,d[ind].up,d[ind].down);
    d[ind].up = 0, d[ind].down = INF;
    int mid = l+r>>1;
    query(ind<<1,l,mid);
    query(ind<<1|1,mid+1,r);
}

void buildWall(int X, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    
    n = X;

    for(int i = 0;i < k;++i) {
        
        op[i]--;
        
            
        range_modify(op[i], left[i], right[i], height[i],1,0,n);
    }
    query(1,0,n);
    forn(i, n) finalHeight[i] = ans[i];
    
    // 

  return;
}

Compilation message (stderr)

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

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