oj.uz

Submission #257418

# Submission time Handle Problem Language Result Execution time Memory
257418 2020-08-04T08:56:17 Z KoD Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 857 ms 43124 KB 
#line 1 "main.cpp"

/**
 * @title Template
 */

#line 1 "rainbow.h"

#ifdef LOCAL
#ifndef __RAINBOW_H
#define __RAINBOW_H

#include <cstdint>

void init(int32_t R, int32_t C, int32_t sr, int32_t sc, int32_t M, char * S);
int32_t colour(int32_t ar, int32_t ac, int32_t br, int32_t bc);

#endif  // __RAINBOW_H
#endif
#line 7 "main.cpp"
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#include <set>
#include <map>

#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/chmin_chmax.cpp"

template <class T, class U>
constexpr bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) { 
    lhs = rhs; 
    return true; 
  }
  return false;
}

template <class T, class U>
constexpr bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) { 
    lhs = rhs; 
    return true; 
  }
  return false;
}

/**
 * @title Chmin/Chmax
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"

class range {
public:
  class iterator {
  private:
    int64_t M_position;

  public:
    constexpr iterator(int64_t position) noexcept: M_position(position) { }
    constexpr void operator ++ () noexcept { ++M_position; }
    constexpr bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
    constexpr int64_t operator * () const noexcept { return M_position; }

  };

  class reverse_iterator {
  private:
    int64_t M_position;
  
  public:
    constexpr reverse_iterator(int64_t position) noexcept: M_position(position) { }
    constexpr void operator ++ () noexcept { --M_position; }
    constexpr bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
    constexpr int64_t operator * () const noexcept { return M_position; }

  };
  
private:
  const iterator M_first, M_last;

public:
  constexpr range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
  constexpr iterator begin() const noexcept { return M_first; }
  constexpr iterator end() const noexcept { return M_last; }
  constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); } 
  constexpr reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); } 

};

/**
 * @title Range
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"

#include <type_traits>
#include <iterator>
#line 6 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"

template <class T>
class rev_impl {
public:
  using iterator = typename std::decay<T>::type::reverse_iterator;

private:
  const iterator M_begin;
  const iterator M_end;

public:
  constexpr rev_impl(T &&cont) noexcept: M_begin(std::rbegin(cont)), M_end(std::rend(cont)) { }
  constexpr iterator begin() const noexcept { return M_begin; }
  constexpr iterator end() const noexcept { return M_end; }

};

template <class T>
constexpr decltype(auto) rev(T &&cont) {
  return rev_impl<T>(std::forward<T>(cont));
}

/**
 * @title Reverser
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp"

#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp"

template <class Func>
struct fix_point_impl: private Func {
  explicit constexpr fix_point_impl(Func &&func): Func(std::forward<Func>(func)) { }
  template <class... Args>
  constexpr decltype(auto) operator () (Args &&... args) const {
    return Func::operator()(*this, std::forward<Args>(args)...);
  }
};

template <class Func>
constexpr decltype(auto) fix_point(Func &&func) {
  return fix_point_impl<Func>(std::forward<Func>(func));
}

/**
 * @title Lambda Recursion
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/container/wavelet_matrix.cpp"

#line 2 "/Users/kodamankod/Desktop/Programming/Library/container/bit_vector.cpp"

#include <cstddef>
#include <cstdint>
#line 7 "/Users/kodamankod/Desktop/Programming/Library/container/bit_vector.cpp"

class bit_vector {
public:
  using size_type = size_t;
  using bit_type = uint64_t;
  using count_type = uint32_t;

private:
  static constexpr size_type S_block_size = 64;

  size_type M_size;
  std::vector<bit_type> M_block;
  std::vector<count_type> M_accum;

public:
  bit_vector() = default;
  template <class InputIterator>
  explicit bit_vector(InputIterator first, InputIterator last) { construct(first, last); }

  template <class InputIterator>
  void construct(InputIterator first, InputIterator last) { 
    M_size = std::distance(first, last);
    size_type fixed_size = M_size / S_block_size + 1;
    M_block.assign(fixed_size, 0);
    M_accum.assign(fixed_size, 0);
    for (size_type i = 0; i < M_size; ++i) {
      M_block[i / S_block_size] |= (bit_type(*first) & 1) << (i & (S_block_size - 1));
      ++first;
    }
    for (size_type i = 1; i < fixed_size; ++i) {
      M_accum[i] = M_accum[i - 1] + __builtin_popcountll(M_block[i - 1]);
    }
  }

  bool access(size_type idx) const {
    return M_block[idx / S_block_size] >> (idx & (S_block_size - 1)) & 1;
  }
  size_type rank(bool value, size_type idx) const {
    bit_type mask = (bit_type(1) << (idx & (S_block_size - 1))) - 1;
    size_type res = M_accum[idx / S_block_size] + __builtin_popcountll(M_block[idx / S_block_size] & mask);
    return value ? res : idx - res;
  }
  size_type select(bool value, size_type idx) const {
    if (idx >= rank(value, M_size)) {
      return M_size;
    }
    size_type ok = 0, ng = M_size;
    while (ng - ok > 1) {
      size_type md = (ok + ng) >> 1;
      (rank(value, md) <= idx ? ok : ng) = md;
    }
    return ok;
  }
  size_type select(bool value, size_type idx, size_type l) const {
    return select(value, idx + rank(value, l));
  }

};

/**
 * @title Succinct Bit Vector
 */
#line 6 "/Users/kodamankod/Desktop/Programming/Library/container/wavelet_matrix.cpp"

template <class T, size_t W>
class wavelet_matrix {
public:
  using value_type = T;
  using size_type = size_t;

  static constexpr size_type word_size = W;

private:
  size_type M_size;
  std::array<bit_vector, word_size> M_fid;
  std::array<size_type, word_size> M_zero;

public:
  wavelet_matrix() = default;
  template <class InputIterator>
  explicit wavelet_matrix(InputIterator first, InputIterator last) { construct(first, last); }

  template <class InputIterator>
  void construct(InputIterator first, InputIterator last) { 
    M_size = std::distance(first, last);
    std::vector<bool> bit(M_size);
    std::vector<value_type> current(first, last);
    std::vector<value_type> next(M_size);
    for (size_type k = word_size; k--;) {
      auto l = next.begin(), r = next.rbegin();
      for (size_type i = 0; i < M_size; ++i) {
        bit[i] = current[i] >> k & 1;
        (bit[i] ? *(r++) : *(l++)) = current[i];
      }
      M_fid[k].construct(bit.begin(), bit.end());
      M_zero[k] = l - next.begin();
      std::reverse(next.rbegin(), r);
      current.swap(next);
    }
  }

  size_type rank(value_type value, size_type l, size_type r) const {
    for (size_type k = word_size; k--;) {
      bool p = value >> k & 1;
      l = M_fid[k].rank(p, l) + p * M_zero[k];
      r = M_fid[k].rank(p, r) + p * M_zero[k];
    }
    return r - l;
  }

  size_type select(value_type value, size_type index) const {
    std::array<size_type, word_size + 1> l, r;
    l[word_size] = 0;
    r[word_size] = M_size;
    for (size_type k = word_size; k--;) {
      bool p = value >> k & 1;
      l[k] = M_fid[k].rank(p, l[k + 1]) + p * M_zero[k];
      r[k] = M_fid[k].rank(p, r[k + 1]) + p * M_zero[k];
    }
    if (r[0] - l[0] <= index) {
      return M_size;
    }
    for (size_type k = 0; k < word_size; ++k) {
      bool p = value >> k & 1;
      index = M_fid[k].select(p, index, l[k + 1]) - l[k + 1];
    }
    return index;
  }

  value_type access(size_type index) const {
    value_type res = 0;
    for (size_type k = word_size; k--;) {
      bool p = M_fid[k].access(index);
      res |= value_type(p) << k;
      index = M_fid[k].rank(p, index) + p * M_zero[k];
    }
    return res;
  }

  value_type quantile(size_type index, size_type l, size_type r) const {
    value_type res = 0;
    for (size_type k = word_size; k--;) {
      size_type lc = M_fid[k].rank(1, l);
      size_type rc = M_fid[k].rank(1, r);
      size_type zc = (r - l) - (rc - lc);
      bool p = (index >= zc);
      res |= value_type(p) << k;
      if (p) {
        l = lc + M_zero[k];
        r = rc + M_zero[k];
        index -= zc;
      }
      else {
        l -= lc;
        r -= rc;
      }
    }
    return res;
  }

  size_type count(size_type l, size_type r, value_type value) const {
    size_type res = 0;
    for (size_type k = word_size; k--;) {
      size_type lc = M_fid[k].rank(1, l);
      size_type rc = M_fid[k].rank(1, r);
      if (value >> (k) & 1) {
        l = lc + M_zero[k];
        r = rc + M_zero[k];
      }
      else {
        l -= lc;
        r -= rc;
        res += (rc - lc);
      }
    }
    return res + (r - l);
  }
  size_type count(size_type l, size_type r, value_type lb, value_type ub) const {
    return count(l, r, lb) - count(l, r, ub);
  }

};

/**
 * @title Wavelet Matrix
 */
#line 22 "main.cpp"

using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;

constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;

constexpr i32 dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
constexpr i32 dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 };

struct count_points {
  wavelet_matrix<i32, 20> matrix;
  std::set<std::pair<i32, i32>> points;
  std::vector<i32> X;
  void add_point(i32 x, i32 y) {
    points.emplace(x, y);
  }
  void build() {
    std::vector<i32> Y;
    for (auto [x, y]: points) {
      X.push_back(x);
      Y.push_back(y);
    }
    matrix.construct(Y.begin(), Y.end());
  }
  i32 count(i32 l, i32 r, i32 lb, i32 ub) {
    if (l >= r || lb >= ub) return 0;
    i32 il = std::lower_bound(X.begin(), X.end(), l) - X.begin();
    i32 ir = std::lower_bound(X.begin(), X.end(), r) - X.begin();
    return matrix.count(il, ir, lb, ub);
  }
};

i32 H, W;
i32 query_counter;
count_points nov, noe_h, noe_w, noc;
std::set<std::pair<i32, i32>> river;

void disable(i32 x, i32 y) {
  river.emplace(x, y);
  nov.add_point(x, y);
  noe_h.add_point(x, y);
  noe_h.add_point(x - 1, y);
  noe_w.add_point(x, y);
  noe_w.add_point(x, y - 1);
  noc.add_point(x, y);
  noc.add_point(x - 1, y);
  noc.add_point(x, y - 1);
  noc.add_point(x - 1, y - 1);
}
 
bool adjacent(i32 x, i32 y) {
  if (river.find(std::make_pair(x, y)) != river.end()) {
    return false;
  }
  for (auto k: range(0, 8)) {
    if (river.find(std::make_pair(x + dx[k], y + dy[k])) != river.end()) {
      return true;
    }
  }
  return false;
}
 
void init(i32 R, i32 C, i32 sr, i32 sc, i32 M, char * S) {
  H = R, W = C;
  {
    i32 x = sr - 1, y = sc - 1;
    disable(x, y);
    for (auto i: range(0, M)) {
      char c = S[i];
      if (c == 'N') --x;
      if (c == 'E') ++y;
      if (c == 'W') --y;
      if (c == 'S') ++x;
      disable(x, y);
    }
  }
  nov.build();
  noe_h.build();
  noe_w.build();
  noc.build();
}
 
i32 colour(i32 ar, i32 ac, i32 br, i32 bc) {
  ++query_counter;
  --ar; --ac; --br; --bc;
  i64 V = (i64) (br - ar + 1) * (bc - ac + 1);
  i64 E = (i64) (br - ar) * (bc - ac + 1) + (i64) (bc - ac) * (br - ar + 1);
  i64 C = (i64) (br - ar) * (bc - ac);
  i32 tmp = nov.count(ar, br + 1, ac, bc + 1);
  if (tmp == 0) {
    return 1;
  }
  i32 tmp2 = nov.count(ar + 1, br, ac + 1, bc);
  if (tmp2 == tmp) {
    ++C;
  }
  V -= nov.count(ar, br + 1, ac, bc + 1);
  E -= noe_h.count(ar, br, ac, bc + 1);
  E -= noe_w.count(ar, br + 1, ac, bc);
  C -= noc.count(ar, br, ac, bc);
  return C - E + V;
}

#ifdef LOCAL

#include <stdio.h>

static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];

int main() {
    scanf("%d %d %d %d", &R, &C, &M, &Q);
    scanf("%d %d", &sr, &sc);
    if (M > 0) {
        scanf(" %s ", S);
    }

    init(R, C, sr, sc, M, S);

    int query;
    for (query = 0; query < Q; query++) {
        int ar, ac, br, bc;
        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        printf("%d\n", colour(ar, ac, br, bc));
    }

    return 0;
}

#endif

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 9 ms 640 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 7 ms 768 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 8 ms 640 KB Output is correct
13 Correct 8 ms 896 KB Output is correct
14 Correct 9 ms 1024 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 437 ms 24420 KB Output is correct
4 Correct 646 ms 40896 KB Output is correct
5 Correct 640 ms 41184 KB Output is correct
6 Correct 574 ms 31608 KB Output is correct
7 Correct 594 ms 30552 KB Output is correct
8 Correct 216 ms 1144 KB Output is correct
9 Correct 634 ms 40780 KB Output is correct
10 Correct 677 ms 41248 KB Output is correct
11 Correct 600 ms 31600 KB Output is correct
12 Correct 504 ms 37836 KB Output is correct
13 Correct 516 ms 40768 KB Output is correct
14 Correct 583 ms 41212 KB Output is correct
15 Correct 564 ms 31524 KB Output is correct
16 Correct 492 ms 29788 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 373 ms 40656 KB Output is correct
3 Correct 371 ms 41052 KB Output is correct
4 Correct 364 ms 40296 KB Output is correct
5 Correct 289 ms 30732 KB Output is correct
6 Correct 152 ms 8200 KB Output is correct
7 Correct 246 ms 15872 KB Output is correct
8 Correct 373 ms 36700 KB Output is correct
9 Correct 352 ms 32740 KB Output is correct
10 Correct 117 ms 8652 KB Output is correct
11 Correct 244 ms 20380 KB Output is correct
12 Correct 371 ms 40768 KB Output is correct
13 Correct 362 ms 41132 KB Output is correct
14 Correct 351 ms 40324 KB Output is correct
15 Correct 281 ms 30708 KB Output is correct
16 Correct 130 ms 6684 KB Output is correct
17 Correct 218 ms 15868 KB Output is correct
18 Correct 348 ms 40436 KB Output is correct
19 Correct 355 ms 40424 KB Output is correct
20 Correct 352 ms 40324 KB Output is correct
21 Correct 359 ms 36700 KB Output is correct
22 Correct 395 ms 32744 KB Output is correct
23 Correct 109 ms 8732 KB Output is correct
24 Correct 243 ms 20376 KB Output is correct
25 Correct 405 ms 40768 KB Output is correct
26 Correct 434 ms 41264 KB Output is correct
27 Correct 440 ms 40372 KB Output is correct
28 Correct 284 ms 30708 KB Output is correct
29 Correct 133 ms 6684 KB Output is correct
30 Correct 227 ms 15856 KB Output is correct
31 Correct 393 ms 40400 KB Output is correct
32 Correct 357 ms 40404 KB Output is correct
33 Correct 354 ms 40328 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 9 ms 640 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 7 ms 768 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 8 ms 640 KB Output is correct
13 Correct 8 ms 896 KB Output is correct
14 Correct 9 ms 1024 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 803 ms 24172 KB Output is correct
19 Correct 193 ms 4676 KB Output is correct
20 Correct 198 ms 3940 KB Output is correct
21 Correct 174 ms 4088 KB Output is correct
22 Correct 177 ms 4352 KB Output is correct
23 Correct 176 ms 4728 KB Output is correct
24 Correct 261 ms 4088 KB Output is correct
25 Correct 205 ms 4216 KB Output is correct
26 Correct 187 ms 4468 KB Output is correct
27 Correct 503 ms 20568 KB Output is correct
28 Correct 478 ms 11940 KB Output is correct
29 Correct 585 ms 19076 KB Output is correct
30 Correct 857 ms 42244 KB Output is correct
31 Correct 7 ms 512 KB Output is correct
32 Correct 750 ms 20900 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 9 ms 640 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 7 ms 768 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 8 ms 640 KB Output is correct
13 Correct 8 ms 896 KB Output is correct
14 Correct 9 ms 1024 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 803 ms 24172 KB Output is correct
19 Correct 193 ms 4676 KB Output is correct
20 Correct 198 ms 3940 KB Output is correct
21 Correct 174 ms 4088 KB Output is correct
22 Correct 177 ms 4352 KB Output is correct
23 Correct 176 ms 4728 KB Output is correct
24 Correct 261 ms 4088 KB Output is correct
25 Correct 205 ms 4216 KB Output is correct
26 Correct 187 ms 4468 KB Output is correct
27 Correct 503 ms 20568 KB Output is correct
28 Correct 478 ms 11940 KB Output is correct
29 Correct 585 ms 19076 KB Output is correct
30 Correct 857 ms 42244 KB Output is correct
31 Correct 7 ms 512 KB Output is correct
32 Correct 750 ms 20900 KB Output is correct
33 Correct 373 ms 40656 KB Output is correct
34 Correct 371 ms 41052 KB Output is correct
35 Correct 364 ms 40296 KB Output is correct
36 Correct 289 ms 30732 KB Output is correct
37 Correct 152 ms 8200 KB Output is correct
38 Correct 246 ms 15872 KB Output is correct
39 Correct 373 ms 36700 KB Output is correct
40 Correct 352 ms 32740 KB Output is correct
41 Correct 117 ms 8652 KB Output is correct
42 Correct 244 ms 20380 KB Output is correct
43 Correct 371 ms 40768 KB Output is correct
44 Correct 362 ms 41132 KB Output is correct
45 Correct 351 ms 40324 KB Output is correct
46 Correct 281 ms 30708 KB Output is correct
47 Correct 130 ms 6684 KB Output is correct
48 Correct 218 ms 15868 KB Output is correct
49 Correct 348 ms 40436 KB Output is correct
50 Correct 355 ms 40424 KB Output is correct
51 Correct 352 ms 40324 KB Output is correct
52 Correct 359 ms 36700 KB Output is correct
53 Correct 395 ms 32744 KB Output is correct
54 Correct 109 ms 8732 KB Output is correct
55 Correct 243 ms 20376 KB Output is correct
56 Correct 405 ms 40768 KB Output is correct
57 Correct 434 ms 41264 KB Output is correct
58 Correct 440 ms 40372 KB Output is correct
59 Correct 284 ms 30708 KB Output is correct
60 Correct 133 ms 6684 KB Output is correct
61 Correct 227 ms 15856 KB Output is correct
62 Correct 393 ms 40400 KB Output is correct
63 Correct 357 ms 40404 KB Output is correct
64 Correct 354 ms 40328 KB Output is correct
65 Correct 760 ms 38816 KB Output is correct
66 Correct 796 ms 35060 KB Output is correct
67 Correct 456 ms 11860 KB Output is correct
68 Correct 628 ms 24032 KB Output is correct
69 Correct 613 ms 42000 KB Output is correct
70 Correct 647 ms 42484 KB Output is correct
71 Correct 562 ms 43124 KB Output is correct
72 Correct 508 ms 33656 KB Output is correct
73 Correct 318 ms 10272 KB Output is correct
74 Correct 366 ms 19104 KB Output is correct
75 Correct 506 ms 42432 KB Output is correct
76 Correct 639 ms 42344 KB Output is correct
77 Correct 826 ms 42984 KB Output is correct
78 Correct 437 ms 24420 KB Output is correct
79 Correct 646 ms 40896 KB Output is correct
80 Correct 640 ms 41184 KB Output is correct
81 Correct 574 ms 31608 KB Output is correct
82 Correct 594 ms 30552 KB Output is correct
83 Correct 216 ms 1144 KB Output is correct
84 Correct 634 ms 40780 KB Output is correct
85 Correct 677 ms 41248 KB Output is correct
86 Correct 600 ms 31600 KB Output is correct
87 Correct 504 ms 37836 KB Output is correct
88 Correct 516 ms 40768 KB Output is correct
89 Correct 583 ms 41212 KB Output is correct
90 Correct 564 ms 31524 KB Output is correct
91 Correct 492 ms 29788 KB Output is correct