제출 #930529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930529		Der_Vlapos	Wall (IOI14_wall)	C++17	32 / 100	3063 ms	186956 KiB

wall

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

using namespace std;

#define f first
#define s second
#define pii pair<int, int>
#define ll long long

const int BIG = 2e9 + 500;

struct segTree
{
  struct Node
  {
    deque<pii> ops;
  };
  vector<Node> tree;
  int sz;

  void init(int n)
  {
    sz = 1;
    while (sz < n)
      sz *= 2;
    tree.resize(2 * sz);
  }

  // 0 - min=
  // 1 - max=

  void upd(int v, int lv, int rv, pii op)
  {
    // cout << lv << " " << rv << " " << op.f << " " << op.s << "!!!\n";
    if (tree[v].ops.size() and op.f == tree[v].ops.back().f)
      tree[v].ops.back().s = (op.f == 0 ? min(op.s, tree[v].ops.back().s) : max(op.s, tree[v].ops.back().s));
    else if (tree[v].ops.size() < 2)
      tree[v].ops.push_back(op);
    else
    {
      if (op.f == 1)
      {
        int C1 = tree[v].ops.begin()->s;
        tree[v].ops.pop_front();
        int C2 = tree[v].ops.begin()->s;
        int C3 = op.s;
        tree[v].ops.push_back({1, max(min(C1, C2), C3)});
      }
      else
      {
        int C1 = tree[v].ops.begin()->s;
        tree[v].ops.pop_front();
        int C2 = tree[v].ops.begin()->s;
        int C3 = op.s;
        tree[v].ops.push_back({0, min(max(C1, C2), C3)});
      }
    }
  }

  void push(int v, int lv, int rv)
  {
    if (rv - lv == 1)
      return;
    int m = (lv + rv) >> 1;
    while (tree[v].ops.size())
    {
      pii op = tree[v].ops.front();
      tree[v].ops.pop_front();
      upd(v * 2 + 1, lv, m, op);
      upd(v * 2 + 2, m, rv, op);
    }
  }

  void addOp(int l, int r, pii op, int v, int lv, int rv)
  {
    push(v, lv, rv);
    if (l <= lv and rv <= r)
    {
      upd(v, lv, rv, op);
      return;
    }
    if (rv <= l or r <= lv)
      return;
    int m = (lv + rv) >> 1;
    addOp(l, r, op, v * 2 + 1, lv, m);
    addOp(l, r, op, v * 2 + 2, m, rv);
  }

  void addOp(int l, int r, pii op)
  {
    addOp(l, r, op, 0, 0, sz);
  }

  void outArray(vector<int> &a, int v, int lv, int rv)
  {
    push(v, lv, rv);
    if (rv - lv == 1)
    {
      if (lv < a.size())
      {
        while (tree[v].ops.size())
        {
          pii op = tree[v].ops.front();
          tree[v].ops.pop_front();
          a[lv] = op.f ? max(a[lv], op.s) : min(a[lv], op.s);
        }
      }
      return;
    }
    int m = (lv + rv) >> 1;
    outArray(a, v * 2 + 1, lv, m);
    outArray(a, v * 2 + 2, m, rv);
  }

  void outArray(vector<int> &a)
  {
    outArray(a, 0, 0, sz);
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  vector<int> a;
  for (int i = 0; i < n; ++i)
    a.push_back(finalHeight[i]);

  segTree tree;
  tree.init(n);

  for (int i = 0; i < k; ++i)
  {
    op[i]--;
    tree.addOp(left[i], right[i] + 1, {1 - op[i], height[i]});
  }

  tree.outArray(a);

  for (int i = 0; i < n; ++i)
    finalHeight[i] = a[i];

  return;
}

컴파일 시 표준 에러 (stderr) 메시지

wall.cpp: In member function 'void segTree::outArray(std::vector<int>&, int, int, int)':
wall.cpp:100:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |       if (lv < a.size())
      |           ~~~^~~~~~~~~~

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