oj.uz

Submission #930538

# Submission time Handle Problem Language Result Execution time Memory
930538 2024-02-20T05:54:26 Z Der_Vlapos Wall (IOI14_wall) C++17
32 / 100
 3000 ms 191936 KB 
#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
  {
    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)});
      }
    }
    assert(tree[v].ops.size() <= 2);
  }

  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);
    }
    assert(tree[v].ops.size() == 0);
  }

  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;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 3 ms 1112 KB Output is correct
4 Correct 26 ms 22620 KB Output is correct
5 Correct 20 ms 22620 KB Output is correct
6 Correct 18 ms 22620 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 112 ms 11244 KB Output is correct
3 Correct 399 ms 49744 KB Output is correct
4 Correct 1908 ms 191208 KB Output is correct
5 Correct 387 ms 190780 KB Output is correct
6 Correct 379 ms 189900 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 ms 1112 KB Output is correct
4 Correct 27 ms 22620 KB Output is correct
5 Correct 19 ms 22528 KB Output is correct
6 Correct 18 ms 22620 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 99 ms 11088 KB Output is correct
9 Correct 391 ms 50120 KB Output is correct
10 Correct 2036 ms 191220 KB Output is correct
11 Correct 401 ms 190668 KB Output is correct
12 Correct 379 ms 190004 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 105 ms 11260 KB Output is correct
15 Correct 121 ms 45780 KB Output is correct
16 Execution timed out 3028 ms 191936 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 1112 KB Output is correct
4 Correct 35 ms 22748 KB Output is correct
5 Correct 20 ms 22616 KB Output is correct
6 Correct 16 ms 22620 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 100 ms 11344 KB Output is correct
9 Correct 454 ms 50108 KB Output is correct
10 Correct 2393 ms 191200 KB Output is correct
11 Correct 398 ms 190668 KB Output is correct
12 Correct 401 ms 190008 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 105 ms 11160 KB Output is correct
15 Correct 128 ms 45652 KB Output is correct
16 Execution timed out 3020 ms 191892 KB Time limit exceeded
17 Halted 0 ms 0 KB -