Submission #1284036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284036		DeltaStruct	Wall (IOI14_wall)	C++20	0 / 100	107 ms	8252 KiB

wall

#include <bits/stdc++.h>
using namespace std;
#include "wall.h"

struct fop {
  int o,x;
  fop() : o(0),x(-1) {}
  fop(int a,int b) : o(a),x(b) {}
  int operator()(int y){
    assert(o==0||x!=-1);
    if (o==0) return y;
    if (o==1) return max(y,x);
    return min(y,x);
  }
};

void buildWall(int n,int q,int op[],int left[],int right[],int height[],int finalHeight[]){
  vector<pair<fop,fop>> segtree(2*n);
  auto f = [&](pair<fop,fop> x,pair<fop,fop> y) -> pair<fop,fop> {
    if (x.first.o==0) return y;
    if (y.first.o==0) return x;
    if (x.second.o==0) x.second = y.first;
    else if (x.second.o==y.first.o){
      if (x.second.o==1) x.second.x = max(x.second.x,y.first.x);
      else x.second.x = min(x.second.x,y.first.x);
    } else {
      if ((x.second.o==1&&max(x.first.x,x.second.x)>y.first.x)||(x.second.o==2&&min(x.first.x,x.second.x)<y.first.x)){
        swap(x.first,x.second),x.second.x = y.first.x;
      }
    }
    if (x.first.o==x.second.o){
      if (x.first.o==1) x.first.x = max(x.first.x,x.second.x);
      if (x.first.o==2) x.first.x = min(x.first.x,x.second.x);
      x.second = fop();
    }
    if (x.first.o==1&&x.second.o==2&&x.first.x>x.second.x) x.first.x = x.second.x;
    if (x.first.o==2&&x.second.o==1&&x.first.x<x.second.x) x.first.x = x.second.x;
    swap(y.first,y.second);
    if (y.first.o!=0){
      if (x.second.o==y.first.o){
        if (x.second.o==1) x.second.x = max(x.second.x,y.first.x);
        else x.second.x = min(x.second.x,y.first.x);
      } else {
        if ((x.second.o==1&&max(x.first.x,x.second.x)>y.first.x)||(x.second.o==2&&min(x.first.x,x.second.x)<y.first.x)){
          swap(x.first,x.second),x.second.x = y.first.x;
        }
      }
    }
    if (x.first.o==x.second.o){
      if (x.first.o==1) x.first.x = max(x.first.x,x.second.x);
      if (x.first.o==2) x.first.x = min(x.first.x,x.second.x);
      x.second = fop();
    }
    if (x.first.o==1&&x.second.o==2&&x.first.x>x.second.x) x.first.x = x.second.x;
    if (x.first.o==2&&x.second.o==1&&x.first.x<x.second.x) x.first.x = x.second.x;
    return x;
  };
  auto pass = [&](int x) -> void {
    if (x<n) segtree[x<<1] = f(segtree[x<<1],segtree[x]),segtree[x<<1|1] = f(segtree[x<<1|1],segtree[x]);
    segtree[x] = make_pair(fop(),fop());
  };
  for (int i(0);i < q;++i){
    for (int l(21);l;l>>=1) pass((n+left[i])>>l),pass((n+right[i])>>l);
    for (int l(n+left[i]),r(n+right[i]+1);l < r;l>>=1,r>>=1){
      if (l&1) segtree[l] = f(segtree[l],make_pair(fop(op[i],height[i]),fop())),++l;
      if (r&1) --r,segtree[r] = f(segtree[r],make_pair(fop(op[i],height[i]),fop()));
    }
  }
  for (int i(1);i < n;++i) pass(i);
  for (int i(0);i < n;++i) finalHeight[i] = segtree[n+i].second(segtree[n+i].first(0));
}

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