oj.uz

Submission #923829

# Submission time Handle Problem Language Result Execution time Memory
923829 2024-02-07T21:59:06 Z myst6 Wall (IOI14_wall) C++14
100 / 100
 936 ms 151848 KB 
#include <bits/stdc++.h>

using namespace std;

#include "wall.h"

const int maxh = 500'005; 

struct Tag {
  int lo, hi;
  Tag(int _lo, int _hi) : lo(_lo), hi(_hi) {}
  Tag() : lo(0), hi(maxh) {}
  void apply(Tag &tag) {
    int newlo = min(max(lo, tag.lo), tag.hi);
    int newhi = max(min(hi, tag.hi), tag.lo);
    lo = newlo;
    hi = newhi;
  }
};

struct Tree {
  vector<Tag> tag, info;
  Tree(int size) { tag.resize(size*4); info.resize(size*4); }
  void pushdown(int x) {
    info[x].apply(tag[x]);
    if (x*2 < tag.size()) tag[x*2].apply(tag[x]);
    if (x*2+1 < tag.size()) tag[x*2+1].apply(tag[x]);
    tag[x] = {};
  }
  void update(int l, int r, int x, int xl, int xr, Tag delta) {
    if (l > r) return;
    pushdown(x); // order matters
    if (l == xl && r == xr) {
      tag[x].apply(delta);
    } else {
      int xm = (xl + xr) / 2;
      update(l, min(r, xm), x*2, xl, xm, delta);
      update(max(l, xm+1), r, x*2+1, xm+1, xr, delta);
      // there is no merging
    }
  }
  Tag query(int v, int x, int xl, int xr) {
    pushdown(x);
    if (xl == xr) {
      return info[x];
    } else {
      int xm = (xl + xr) / 2;
      if (v <= xm) return query(v, x*2, xl, xm);
      else return query(v, x*2+1, xm+1, xr);
    }
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  Tree tree(n);
  for (int i=0; i<k; i++) {
    if (op[i] == 1) {
      // adding phase
      tree.update(left[i], right[i], 1, 0, n-1, {height[i], maxh});
    } else {
      // removing phase
      tree.update(left[i], right[i], 1, 0, n-1, {0, height[i]});
    }
  }
  for (int i=0; i<n; i++) {
    Tag tag = tree.query(i, 1, 0, n-1);
    finalHeight[i] = tag.lo;
  }
}

Compilation message

wall.cpp: In member function 'void Tree::pushdown(int)':
wall.cpp:26:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tag>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if (x*2 < tag.size()) tag[x*2].apply(tag[x]);
      |         ~~~~^~~~~~~~~~~~
wall.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tag>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if (x*2+1 < tag.size()) tag[x*2+1].apply(tag[x]);
      |         ~~~~~~^~~~~~~~~~~~

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 2 ms 348 KB Output is correct
4 Correct 8 ms 1116 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 6 ms 1116 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 120 ms 13932 KB Output is correct
3 Correct 184 ms 5524 KB Output is correct
4 Correct 557 ms 24392 KB Output is correct
5 Correct 239 ms 24888 KB Output is correct
6 Correct 248 ms 23448 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 572 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 9 ms 1144 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 111 ms 14036 KB Output is correct
9 Correct 181 ms 8660 KB Output is correct
10 Correct 545 ms 24388 KB Output is correct
11 Correct 247 ms 24984 KB Output is correct
12 Correct 242 ms 23508 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 119 ms 14276 KB Output is correct
15 Correct 39 ms 2396 KB Output is correct
16 Correct 664 ms 24388 KB Output is correct
17 Correct 260 ms 23780 KB Output is correct
18 Correct 281 ms 23888 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 8 ms 1112 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 5 ms 1112 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 112 ms 14028 KB Output is correct
9 Correct 185 ms 8528 KB Output is correct
10 Correct 531 ms 24388 KB Output is correct
11 Correct 258 ms 25168 KB Output is correct
12 Correct 241 ms 23420 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 116 ms 13980 KB Output is correct
15 Correct 38 ms 2584 KB Output is correct
16 Correct 690 ms 24624 KB Output is correct
17 Correct 282 ms 23928 KB Output is correct
18 Correct 274 ms 23892 KB Output is correct
19 Correct 918 ms 151636 KB Output is correct
20 Correct 934 ms 151560 KB Output is correct
21 Correct 906 ms 151824 KB Output is correct
22 Correct 936 ms 151804 KB Output is correct
23 Correct 899 ms 151636 KB Output is correct
24 Correct 907 ms 151688 KB Output is correct
25 Correct 907 ms 151628 KB Output is correct
26 Correct 897 ms 151756 KB Output is correct
27 Correct 908 ms 151848 KB Output is correct
28 Correct 918 ms 151672 KB Output is correct
29 Correct 902 ms 151636 KB Output is correct
30 Correct 910 ms 151772 KB Output is correct