답안 #257377

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
257377	2020-08-04T07:46:58 Z	KoD	무지개나라 (APIO17_rainbow)	C++17	100 / 100	1262 ms	62068 KB

rainbow

#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;
i32 query_all;
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();
  {
    std::set<std::pair<i32, i32>> visited;
    auto dfs = fix_point([&](auto dfs, i32 x, i32 y) -> void {
      if (visited.find(std::make_pair(x, y)) != visited.end()) {
        return;
      }
      visited.insert(std::make_pair(x, y));
      for (auto k: range(0, 4)) {
        i32 nx = x + dx[k], ny = y + dy[k];
        if (adjacent(nx, ny)) {
          dfs(nx, ny);
        }
      }
    });
    query_all = 0;
    for (auto [x, y]: river) {
      for (auto k: range(0, 4)) {
        i32 nx = x + dx[k], ny = y + dy[k];
        if (adjacent(nx, ny) && visited.find(std::make_pair(nx, ny)) == visited.end()) {
          ++query_all;
          dfs(nx, ny);
        }
      }
    }
  }
}
 
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) {
    return query_all;
  }
  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

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	8 ms	640 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	8 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	9 ms	640 KB	Output is correct
13	Correct	9 ms	896 KB	Output is correct
14	Correct	11 ms	1024 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	0 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	738 ms	35940 KB	Output is correct
4	Correct	976 ms	59452 KB	Output is correct
5	Correct	1044 ms	58668 KB	Output is correct
6	Correct	826 ms	41724 KB	Output is correct
7	Correct	946 ms	41104 KB	Output is correct
8	Correct	221 ms	1528 KB	Output is correct
9	Correct	1025 ms	59416 KB	Output is correct
10	Correct	1101 ms	58584 KB	Output is correct
11	Correct	828 ms	41760 KB	Output is correct
12	Correct	934 ms	55320 KB	Output is correct
13	Correct	953 ms	59324 KB	Output is correct
14	Correct	1002 ms	58564 KB	Output is correct
15	Correct	794 ms	41912 KB	Output is correct
16	Correct	740 ms	42320 KB	Output is correct

Subtask #3

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	913 ms	58440 KB	Output is correct
3	Correct	767 ms	58364 KB	Output is correct
4	Correct	808 ms	58328 KB	Output is correct
5	Correct	603 ms	44008 KB	Output is correct
6	Correct	170 ms	8472 KB	Output is correct
7	Correct	296 ms	16192 KB	Output is correct
8	Correct	631 ms	46328 KB	Output is correct
9	Correct	629 ms	40336 KB	Output is correct
10	Correct	149 ms	9304 KB	Output is correct
11	Correct	473 ms	28696 KB	Output is correct
12	Correct	958 ms	58356 KB	Output is correct
13	Correct	766 ms	58360 KB	Output is correct
14	Correct	802 ms	58216 KB	Output is correct
15	Correct	593 ms	43832 KB	Output is correct
16	Correct	143 ms	6820 KB	Output is correct
17	Correct	257 ms	16028 KB	Output is correct
18	Correct	634 ms	48280 KB	Output is correct
19	Correct	852 ms	58196 KB	Output is correct
20	Correct	812 ms	58156 KB	Output is correct
21	Correct	671 ms	46196 KB	Output is correct
22	Correct	623 ms	40436 KB	Output is correct
23	Correct	144 ms	9300 KB	Output is correct
24	Correct	475 ms	28568 KB	Output is correct
25	Correct	918 ms	58300 KB	Output is correct
26	Correct	783 ms	58424 KB	Output is correct
27	Correct	795 ms	58276 KB	Output is correct
28	Correct	588 ms	43944 KB	Output is correct
29	Correct	139 ms	6812 KB	Output is correct
30	Correct	259 ms	16156 KB	Output is correct
31	Correct	516 ms	48168 KB	Output is correct
32	Correct	803 ms	58304 KB	Output is correct
33	Correct	811 ms	58356 KB	Output is correct

Subtask #4

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	8 ms	640 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	8 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	9 ms	640 KB	Output is correct
13	Correct	9 ms	896 KB	Output is correct
14	Correct	11 ms	1024 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	0 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	963 ms	27636 KB	Output is correct
19	Correct	190 ms	5112 KB	Output is correct
20	Correct	196 ms	3960 KB	Output is correct
21	Correct	172 ms	4184 KB	Output is correct
22	Correct	161 ms	4472 KB	Output is correct
23	Correct	192 ms	4856 KB	Output is correct
24	Correct	249 ms	4088 KB	Output is correct
25	Correct	205 ms	4344 KB	Output is correct
26	Correct	175 ms	4472 KB	Output is correct
27	Correct	543 ms	22088 KB	Output is correct
28	Correct	460 ms	12452 KB	Output is correct
29	Correct	548 ms	19516 KB	Output is correct
30	Correct	960 ms	51656 KB	Output is correct
31	Correct	8 ms	512 KB	Output is correct
32	Correct	764 ms	21032 KB	Output is correct

Subtask #5

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	8 ms	640 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	8 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	9 ms	640 KB	Output is correct
13	Correct	9 ms	896 KB	Output is correct
14	Correct	11 ms	1024 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	0 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	963 ms	27636 KB	Output is correct
19	Correct	190 ms	5112 KB	Output is correct
20	Correct	196 ms	3960 KB	Output is correct
21	Correct	172 ms	4184 KB	Output is correct
22	Correct	161 ms	4472 KB	Output is correct
23	Correct	192 ms	4856 KB	Output is correct
24	Correct	249 ms	4088 KB	Output is correct
25	Correct	205 ms	4344 KB	Output is correct
26	Correct	175 ms	4472 KB	Output is correct
27	Correct	543 ms	22088 KB	Output is correct
28	Correct	460 ms	12452 KB	Output is correct
29	Correct	548 ms	19516 KB	Output is correct
30	Correct	960 ms	51656 KB	Output is correct
31	Correct	8 ms	512 KB	Output is correct
32	Correct	764 ms	21032 KB	Output is correct
33	Correct	913 ms	58440 KB	Output is correct
34	Correct	767 ms	58364 KB	Output is correct
35	Correct	808 ms	58328 KB	Output is correct
36	Correct	603 ms	44008 KB	Output is correct
37	Correct	170 ms	8472 KB	Output is correct
38	Correct	296 ms	16192 KB	Output is correct
39	Correct	631 ms	46328 KB	Output is correct
40	Correct	629 ms	40336 KB	Output is correct
41	Correct	149 ms	9304 KB	Output is correct
42	Correct	473 ms	28696 KB	Output is correct
43	Correct	958 ms	58356 KB	Output is correct
44	Correct	766 ms	58360 KB	Output is correct
45	Correct	802 ms	58216 KB	Output is correct
46	Correct	593 ms	43832 KB	Output is correct
47	Correct	143 ms	6820 KB	Output is correct
48	Correct	257 ms	16028 KB	Output is correct
49	Correct	634 ms	48280 KB	Output is correct
50	Correct	852 ms	58196 KB	Output is correct
51	Correct	812 ms	58156 KB	Output is correct
52	Correct	671 ms	46196 KB	Output is correct
53	Correct	623 ms	40436 KB	Output is correct
54	Correct	144 ms	9300 KB	Output is correct
55	Correct	475 ms	28568 KB	Output is correct
56	Correct	918 ms	58300 KB	Output is correct
57	Correct	783 ms	58424 KB	Output is correct
58	Correct	795 ms	58276 KB	Output is correct
59	Correct	588 ms	43944 KB	Output is correct
60	Correct	139 ms	6812 KB	Output is correct
61	Correct	259 ms	16156 KB	Output is correct
62	Correct	516 ms	48168 KB	Output is correct
63	Correct	803 ms	58304 KB	Output is correct
64	Correct	811 ms	58356 KB	Output is correct
65	Correct	1084 ms	49904 KB	Output is correct
66	Correct	1050 ms	44148 KB	Output is correct
67	Correct	464 ms	12856 KB	Output is correct
68	Correct	808 ms	32280 KB	Output is correct
69	Correct	1123 ms	61988 KB	Output is correct
70	Correct	1002 ms	61948 KB	Output is correct
71	Correct	977 ms	62068 KB	Output is correct
72	Correct	805 ms	47516 KB	Output is correct
73	Correct	284 ms	10416 KB	Output is correct
74	Correct	396 ms	19764 KB	Output is correct
75	Correct	648 ms	51652 KB	Output is correct
76	Correct	1077 ms	61944 KB	Output is correct
77	Correct	1262 ms	61940 KB	Output is correct
78	Correct	738 ms	35940 KB	Output is correct
79	Correct	976 ms	59452 KB	Output is correct
80	Correct	1044 ms	58668 KB	Output is correct
81	Correct	826 ms	41724 KB	Output is correct
82	Correct	946 ms	41104 KB	Output is correct
83	Correct	221 ms	1528 KB	Output is correct
84	Correct	1025 ms	59416 KB	Output is correct
85	Correct	1101 ms	58584 KB	Output is correct
86	Correct	828 ms	41760 KB	Output is correct
87	Correct	934 ms	55320 KB	Output is correct
88	Correct	953 ms	59324 KB	Output is correct
89	Correct	1002 ms	58564 KB	Output is correct
90	Correct	794 ms	41912 KB	Output is correct
91	Correct	740 ms	42320 KB	Output is correct