제출 #930551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930551		Der_Vlapos	벽 (IOI14_wall)	C++17	100 / 100	603 ms	73560 KiB

wall

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")

#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
  {
    int mx = 0, mn = BIG, last = 0;
  };

  vector<Node> tree;
  int sz;

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

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

  int C1, C2, C3;

  void upd(int v, pii op)
  {
    if (tree[v].last == op.f)
    {
      if (op.f == 1)
        tree[v].mx = max(tree[v].mx, op.s);
      else
        tree[v].mn = min(tree[v].mn, op.s);
    }
    else
    {
      if (op.f == 1)
      {
        C1 = tree[v].mx;
        C2 = tree[v].mn;
        C3 = op.s;
        tree[v].mx = max(min(C1, C2), C3);
      }
      else
      {
        C1 = tree[v].mn;
        C2 = tree[v].mx;
        C3 = op.s;
        tree[v].mn = min(max(C1, C2), C3);
      }
      tree[v].last = op.f;
    }
  }

  void push(int v)
  {
    if (tree[v].last == 0)
    {
      if (tree[v].mx != 0)
      {
        upd(v * 2 + 1, {1, tree[v].mx});
        upd(v * 2 + 2, {1, tree[v].mx});
      }
      if (tree[v].mn != BIG)
      {
        upd(v * 2 + 1, {0, tree[v].mn});
        upd(v * 2 + 2, {0, tree[v].mn});
      }
    }
    else
    {
      if (tree[v].mn != BIG)
      {
        upd(v * 2 + 1, {0, tree[v].mn});
        upd(v * 2 + 2, {0, tree[v].mn});
      }
      if (tree[v].mx != 0)
      {
        upd(v * 2 + 1, {1, tree[v].mx});
        upd(v * 2 + 2, {1, tree[v].mx});
      }
    }
    tree[v].mx = 0;
    tree[v].mn = BIG;
  }

  void addOp(int l, int r, pii &op, int v, int lv, int rv)
  {
    if (l <= lv and rv <= r)
    {
      upd(v, op);
      return;
    }
    if (rv <= l or r <= lv)
      return;
    int m = (lv + rv) >> 1;
    push(v);
    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)
  {
    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);
        // }
        if (tree[v].last == 0)
        {
          // cout << lv << " " << tree[v].mx << " | " << tree[v].mn << "!\n";
          a[lv] = max(a[lv], tree[v].mx);
          a[lv] = min(a[lv], tree[v].mn);
        }
        else
        {
          // cout << lv << " | " << v << " " << tree[v].mn << " " << tree[v].mx << "!\n";
          a[lv] = min(a[lv], tree[v].mn);
          a[lv] = max(a[lv], tree[v].mx);
        }
      }
      return;
    }
    int m = (lv + rv) >> 1;
    push(v);
    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;
}

// int main()
// {
//   int n;
//   int k;

//   int i, j;
//   int status = 0;

//   status = scanf("%d%d", &n, &k);
//   assert(status == 2);

//   int *op = (int *)calloc(sizeof(int), k);
//   int *left = (int *)calloc(sizeof(int), k);
//   int *right = (int *)calloc(sizeof(int), k);
//   int *height = (int *)calloc(sizeof(int), k);
//   int *finalHeight = (int *)calloc(sizeof(int), n);

//   for (i = 0; i < k; i++)
//   {
//     status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
//     assert(status == 4);
//   }

//   buildWall(n, k, op, left, right, height, finalHeight);

//   for (j = 0; j < n; j++)
//     printf("%d\n", finalHeight[j]);

//   return 0;
// }

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

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

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