oj.uz

Submission #754553

# Submission time Handle Problem Language Result Execution time Memory
754553 2023-06-08T04:43:55 Z marvinthang Wall (IOI14_wall) C++17
100 / 100
 648 ms 94896 KB 
/*************************************
*    author: marvinthang             *
*    created: 08.06.2023 11:30:33    *
*************************************/

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

const int MAX = 2e6 + 6;

struct Node {
    int l, r;
    Node(int l = 0, int r = MAX): l(l), r(r) {}
    Node & operator += (const Node &other) {
        l = max(min(l, other.r), other.l);
        r = max(min(r, other.r), other.l);
        return *this;
    }
    Node operator + (const Node &other) const {
        return Node(*this) += other;
    }
    bool operator == (const Node &other) const {
        return l == other.l && r == other.r;
    }
} lazy[MAX << 2];

void pushDown(int i) {
    if (lazy[i] == Node()) return;
    lazy[i << 1] += lazy[i];
    lazy[i << 1 | 1] += lazy[i];
    lazy[i] = Node();
}

void update(int i, int l, int r, int u, int v, Node x) {
    if (l >= v || r <= u) return;
    if (u <= l && r <= v) {
        lazy[i] += x;
        return;
    }
    int m = l + r >> 1;
    pushDown(i);
    update(i << 1, l, m, u, v, x);
    update(i << 1 | 1, m, r, u, v, x);
}

void get(int i, int l, int r, int res[]) {
    if (r - l == 1) {
        res[l] = lazy[i].l;
        return;
    }
    int m = l + r >> 1;
    pushDown(i);
    get(i << 1, l, m, res);
    get(i << 1 | 1, m, r, res);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    REP(i, k) update(1, 0, n, left[i], right[i] + 1, op[i] == 1 ? Node(height[i], MAX) : Node(0, height[i]));
    get(1, 0, n, finalHeight);
}

#ifdef LOCAL
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "wall.h"

int main()
{
    file("wall");
  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;
}
#endif

Compilation message

wall.cpp: In function 'void update(int, int, int, int, int, Node)':
wall.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     int m = l + r >> 1;
      |             ~~^~~
wall.cpp: In function 'void get(int, int, int, int*)':
wall.cpp:88:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |     int m = l + r >> 1;
      |             ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62908 KB Output is correct
2 Correct 30 ms 62996 KB Output is correct
3 Correct 29 ms 62924 KB Output is correct
4 Correct 34 ms 63104 KB Output is correct
5 Correct 39 ms 63044 KB Output is correct
6 Correct 33 ms 63180 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62908 KB Output is correct
2 Correct 163 ms 73460 KB Output is correct
3 Correct 191 ms 69020 KB Output is correct
4 Correct 533 ms 74464 KB Output is correct
5 Correct 257 ms 74728 KB Output is correct
6 Correct 261 ms 75000 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62864 KB Output is correct
2 Correct 30 ms 62936 KB Output is correct
3 Correct 29 ms 62912 KB Output is correct
4 Correct 34 ms 63056 KB Output is correct
5 Correct 33 ms 63088 KB Output is correct
6 Correct 33 ms 63124 KB Output is correct
7 Correct 30 ms 62916 KB Output is correct
8 Correct 178 ms 76572 KB Output is correct
9 Correct 172 ms 69956 KB Output is correct
10 Correct 494 ms 77228 KB Output is correct
11 Correct 251 ms 77444 KB Output is correct
12 Correct 241 ms 77928 KB Output is correct
13 Correct 29 ms 62840 KB Output is correct
14 Correct 175 ms 76496 KB Output is correct
15 Correct 58 ms 64020 KB Output is correct
16 Correct 568 ms 77584 KB Output is correct
17 Correct 251 ms 77772 KB Output is correct
18 Correct 263 ms 77704 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62916 KB Output is correct
2 Correct 36 ms 62920 KB Output is correct
3 Correct 33 ms 62972 KB Output is correct
4 Correct 34 ms 63040 KB Output is correct
5 Correct 32 ms 63152 KB Output is correct
6 Correct 32 ms 63104 KB Output is correct
7 Correct 33 ms 62896 KB Output is correct
8 Correct 156 ms 76512 KB Output is correct
9 Correct 174 ms 70008 KB Output is correct
10 Correct 513 ms 77248 KB Output is correct
11 Correct 275 ms 77536 KB Output is correct
12 Correct 268 ms 78084 KB Output is correct
13 Correct 29 ms 62796 KB Output is correct
14 Correct 183 ms 76532 KB Output is correct
15 Correct 61 ms 64076 KB Output is correct
16 Correct 536 ms 77584 KB Output is correct
17 Correct 262 ms 77816 KB Output is correct
18 Correct 301 ms 77676 KB Output is correct
19 Correct 540 ms 94700 KB Output is correct
20 Correct 569 ms 92236 KB Output is correct
21 Correct 558 ms 94872 KB Output is correct
22 Correct 566 ms 92476 KB Output is correct
23 Correct 574 ms 92332 KB Output is correct
24 Correct 648 ms 92336 KB Output is correct
25 Correct 561 ms 92404 KB Output is correct
26 Correct 543 ms 94872 KB Output is correct
27 Correct 570 ms 94896 KB Output is correct
28 Correct 557 ms 92348 KB Output is correct
29 Correct 562 ms 92316 KB Output is correct
30 Correct 553 ms 92472 KB Output is correct