oj.uz

Submission #930552

# Submission time Handle Problem Language Result Execution time Memory
930552 2024-02-20T06:24:58 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 508 ms 73516 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
  {
    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;
// }

Compilation message

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.0 / 8.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 1 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 800 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 101 ms 8016 KB Output is correct
3 Correct 139 ms 4504 KB Output is correct
4 Correct 343 ms 12064 KB Output is correct
5 Correct 191 ms 12236 KB Output is correct
6 Correct 189 ms 12012 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 148 ms 8152 KB Output is correct
9 Correct 118 ms 4712 KB Output is correct
10 Correct 323 ms 12124 KB Output is correct
11 Correct 200 ms 12124 KB Output is correct
12 Correct 182 ms 12128 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 104 ms 8048 KB Output is correct
15 Correct 27 ms 1884 KB Output is correct
16 Correct 486 ms 12128 KB Output is correct
17 Correct 202 ms 12120 KB Output is correct
18 Correct 201 ms 12120 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 548 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 7 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 104 ms 8108 KB Output is correct
9 Correct 113 ms 4688 KB Output is correct
10 Correct 326 ms 12124 KB Output is correct
11 Correct 295 ms 12256 KB Output is correct
12 Correct 201 ms 12120 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 109 ms 8020 KB Output is correct
15 Correct 29 ms 1912 KB Output is correct
16 Correct 498 ms 12120 KB Output is correct
17 Correct 201 ms 12124 KB Output is correct
18 Correct 207 ms 12172 KB Output is correct
19 Correct 489 ms 73092 KB Output is correct
20 Correct 475 ms 73176 KB Output is correct
21 Correct 491 ms 73184 KB Output is correct
22 Correct 470 ms 73392 KB Output is correct
23 Correct 478 ms 73184 KB Output is correct
24 Correct 474 ms 73180 KB Output is correct
25 Correct 477 ms 73172 KB Output is correct
26 Correct 481 ms 73212 KB Output is correct
27 Correct 508 ms 73168 KB Output is correct
28 Correct 503 ms 73516 KB Output is correct
29 Correct 502 ms 73180 KB Output is correct
30 Correct 473 ms 73172 KB Output is correct