oj.uz

Submission #930527

# Submission time Handle Problem Language Result Execution time Memory
930527 2024-02-20T05:45:21 Z vjudge1 Wall (IOI14_wall) C++17
32 / 100
 3000 ms 196420 KB 
#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;
}

Compilation message

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.0 / 8.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 1116 KB Output is correct
4 Correct 26 ms 22620 KB Output is correct
5 Correct 17 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 0 ms 348 KB Output is correct
2 Correct 101 ms 8044 KB Output is correct
3 Correct 465 ms 48004 KB Output is correct
4 Correct 2050 ms 195708 KB Output is correct
5 Correct 348 ms 195532 KB Output is correct
6 Correct 355 ms 193996 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 1116 KB Output is correct
4 Correct 28 ms 22756 KB Output is correct
5 Correct 18 ms 22616 KB Output is correct
6 Correct 19 ms 22620 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 106 ms 13924 KB Output is correct
9 Correct 399 ms 51792 KB Output is correct
10 Correct 2077 ms 195680 KB Output is correct
11 Correct 356 ms 195808 KB Output is correct
12 Correct 347 ms 193992 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 107 ms 14064 KB Output is correct
15 Correct 122 ms 45840 KB Output is correct
16 Execution timed out 3048 ms 196384 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 1116 KB Output is correct
4 Correct 26 ms 22788 KB Output is correct
5 Correct 18 ms 22620 KB Output is correct
6 Correct 17 ms 22616 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 105 ms 13984 KB Output is correct
9 Correct 433 ms 51840 KB Output is correct
10 Correct 2241 ms 195716 KB Output is correct
11 Correct 371 ms 195696 KB Output is correct
12 Correct 374 ms 194000 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 107 ms 13884 KB Output is correct
15 Correct 132 ms 45960 KB Output is correct
16 Execution timed out 3065 ms 196420 KB Time limit exceeded
17 Halted 0 ms 0 KB -