Submission #299832

#	Time	Username	Problem	Language	Result	Execution time	Memory
299832		NaimSS	Wall (IOI14_wall)	C++14	0 / 100	183 ms	262148 KiB

wall

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;

typedef pair<ll,ll> pll;
typedef pair<pll,int> T;
const ll INF = 1e18;
// benq segbeats
template<int SZ> struct Seg { // SZ is power of TWO!!
  int N,Q;
  ll mxMod[2*SZ], mnMod[2*SZ], mod[2*SZ];
  T mx[2*SZ], mn[2*SZ]; ll sum[2*SZ];
  Seg() { init(); }
  void init(int ind = 1, int L = 0, int R = SZ-1) {
    mxMod[ind] = INF, mnMod[ind] = -INF, mod[ind] = 0; // OK
    if (L == R) {
      mx[ind] = {{0,-INF},1}; mn[ind] = {{0,INF},1}; sum[ind] = 0;
      return;
    } 
    int M = (L+R)/2;
    init(2*ind,L,M); init(2*ind+1,M+1,R);
    pull(ind);
  }
  T combMn(T a, T b) { // MIN
    if (a > b) swap(a,b);
    if (a.ff.ff == b.ff.ff) return {{a.ff.ff,min(a.ff.ss,b.ff.ss)},a.ss+b.ss};
    return {{a.ff.ff,min(a.ff.ss,b.ff.ff)},a.ss};
  }
  T combMx(T a, T b) {
    if (a < b) swap(a,b);
    if (a.ff.ff == b.ff.ff) return {{a.ff.ff,max(a.ff.ss,b.ff.ss)},a.ss+b.ss};
    return {{a.ff.ff,max(a.ff.ss,b.ff.ff)},a.ss};
  }
  void pull(int ind) { // OK
    sum[ind] = sum[2*ind]+sum[2*ind+1];
    mn[ind] = combMn(mn[2*ind],mn[2*ind+1]);
    mx[ind] = combMx(mx[2*ind],mx[2*ind+1]);
  }

  template<class T> bool ckmin(T& a, const T& b) { 
  return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
  return a < b ? a = b, 1 : 0; } 

  void push(int ind, int L, int R) {
    auto chk = [](ll& a, ll b, ll c) { if (a == b) a = c; };
    if (mnMod[ind] != -INF) {
      if (mnMod[ind] > mn[ind].ff.ff) {
        assert(mnMod[ind] < mn[ind].ff.ss);
        sum[ind] += (mnMod[ind]-mn[ind].ff.ff)*mn[ind].ss;
        chk(mx[ind].ff.ff,mn[ind].ff.ff,mnMod[ind]);
        chk(mx[ind].ff.ss,mn[ind].ff.ff,mnMod[ind]);
        mn[ind].ff.ff = mnMod[ind];
        if (L != R) 
          rep(i,0,2) {
            int pos = 2*ind+i;
            ckmax(mnMod[pos],mnMod[ind]-mod[pos]);
            ckmax(mxMod[pos],mnMod[pos]);
          }
      }
      mnMod[ind] = -INF;
    }
    if (mxMod[ind] != INF) {
      if (mxMod[ind] < mx[ind].ff.ff) {
        assert(mxMod[ind] > mx[ind].ff.ss);
        sum[ind] += (mxMod[ind]-mx[ind].ff.ff)*mx[ind].ss;
        chk(mn[ind].ff.ff,mx[ind].ff.ff,mxMod[ind]);
        chk(mn[ind].ff.ss,mx[ind].ff.ff,mxMod[ind]);
        mx[ind].ff.ff = mxMod[ind];
        if (L != R) 
          rep(i,0,2) {
            int pos = 2*ind+i;
            ckmin(mxMod[pos],mxMod[ind]-mod[pos]);
            ckmin(mnMod[pos],mxMod[pos]);
          }
      }
      mxMod[ind] = INF;
    }
    if (mod[ind] != 0) {
      sum[ind] += mod[ind]*(R-L+1);
      auto inc = [](T& a, ll b) { 
        if (abs(a.ff.ff) != INF) a.ff.ff += b;
        if (abs(a.ff.ss) != INF) a.ff.ss += b; 
      };
      inc(mx[ind],mod[ind]); inc(mn[ind],mod[ind]);
      if (L != R) 
        rep(i,0,2) {
          int pos = 2*ind+i;
          mod[pos] += mod[ind];
        }
      mod[ind] = 0;
    }
  }
  ll query(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
    push(ind,L,R);
    if (R < lo || hi < L) return 0;
    if (lo <= L && R <= hi) {
      //dbg("???",ind,L,R,sum[ind]);
      return sum[ind];
    }
    int M = (L+R)/2;
    return query(lo,hi,2*ind,L,M)+query(lo,hi,2*ind+1,M+1,R);
  }
  void upd(int lo, int hi, int t, ll b, int ind = 1, int L = 0, int R = SZ-1) {
    push(ind,L,R);
    if (R < lo || hi < L) return;
    if (t == 0) {
      if (b >= mx[ind].ff.ff) return;
    } else if (t == 1) {
      if (b <= mn[ind].ff.ff) return;
    }
    if (lo <= L && R <= hi) {
      if (t == 0) {
        if (b > mx[ind].ff.ss) {
          mxMod[ind] = b; 
          push(ind,L,R); return;
        }
      } else if (t == 1) {
        if (b < mn[ind].ff.ss) {
          mnMod[ind] = b;
          push(ind,L,R); return;
        }
      } else if (t == 2) {
        mod[ind] = b;
        push(ind,L,R); return;
      }
    }
    assert(L != R);
    int M = (L+R)/2;
    upd(lo,hi,t,b,2*ind,L,M); upd(lo,hi,t,b,2*ind+1,M+1,R);
    pull(ind);
  }
};
#define CHMIN 0
#define CHMAX 1
#define ADD 2
#define QUERY 3
const int tam = (1<<21);
Seg<tam> seg;

void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
  seg.init();
  for(int i=0;i<k;i++){
    seg.upd(left[i],right[i],(op[i] == 1 ? CHMAX : CHMIN),height[i]);
  } 
  for(int i=0;i<n;i++){
    finalHeight[i] = seg.query(i,i);
  }
}

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