Submission #841726

#	Time	Username	Problem	Language	Result	Execution time	Memory
841726		12345678	Wall (IOI14_wall)	C++17	0 / 100	162 ms	78164 KiB

wall

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

using namespace std;

const int nx=2e6+5;

struct segtree
{
  int ans[nx];
  struct node
  {
    int low, up;
    node(): low(INT_MIN), up(INT_MAX){}
  } d[4*nx];
  void change(int nw, int p)
  {
    d[nw].low=max(d[nw].low, d[p].low);
    d[nw].low=min(d[nw].low, d[p].up);
    d[nw].up=min(d[nw].up, d[p].up);
    d[nw].up=max(d[nw].up, d[p].low);
  }
  void pushlz(int l, int r, int i)
  {
    if (l==r) return;
    change(2*i, i);
    change(2*i+1, i);
    d[i].low=INT_MIN; d[i].up=INT_MAX;
  }
  void add(int l, int r, int i, int ql, int qr, int t)
  {
    pushlz(l, r, i);
    if (qr<l||r<ql) return;
    if (ql<=l&&r<=qr) return d[i].low=t, d[i].up=max(d[i].low, d[i].up), void();
    int md=(l+r)/2;
    add(l, md, 2*i, ql, qr, t);
    add(md+1, r, 2*i+1, ql, qr, t);
    //d[i].low=min(d[i].low, d[i].up);
    //d[i].up=max(d[i].up, d[i].low);
  }
  void remove(int l, int r, int i, int ql, int qr, int t)
  {
    pushlz(l, r, i);
    if (qr<l||r<ql) return;
    if (ql<=l&&r<=qr) return d[i].up=t, d[i].low=min(d[i].low, d[i].up), void();
    int md=(l+r)/2;
    remove(l, md, 2*i, ql, qr, t);
    remove(md+1, r, 2*i+1, ql, qr, t);
  }
  /*
  void show(int l, int r, int i)
  {
    cout<<l<<' '<<r<<' '<<i<<' '<<d[i].low<<' '<<d[i].up<<'\n';
    if (l==r) return;
    show(l, (l+r)/2, 2*i);
    show((l+r)/2+1, r, 2*i+1);
  }*/
  void dfs(int l, int r, int i)
  {
    pushlz(l, r, i);
    if (l==r)
    {
      ans[l]=max(d[i].low, 0);
      return;
    }
    int md=(l+r)/2;
    dfs(l, md, 2*i);
    dfs(md+1, r, 2*i+1);
  }
} s;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for (int i=0; i<k; i++)
  {
    if (op[i]==1) s.add(0, n-1, 1, left[i], right[i], height[i]);
    else s.remove(0, n-1, 1, left[i], right[i], height[i]);
  }
  s.dfs(0, n-1, 1);
  for (int i=0; i<n; i++) finalHeight[i]=s.ans[i];
  return;
}

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