Submission #363824

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
363824	2021-02-07T10:34:48 Z	KoD	Fire (JOI20_ho_t5)	C++17	1 / 100	1000 ms	78356 KB

ho_t5

#line 1 "main.cpp"

/**
 * @title Template
 */

#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#include <stack>

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/container/lazy_propagation_segment_tree.cpp"

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/bit_operation.cpp"

#include <cstddef>
#include <cstdint>

constexpr size_t bit_ppc(const uint64_t x) { return __builtin_popcountll(x); }
constexpr size_t bit_ctzr(const uint64_t x) { return x == 0 ? 64 : __builtin_ctzll(x); }
constexpr size_t bit_ctzl(const uint64_t x) { return x == 0 ? 64 : __builtin_clzll(x); }
constexpr size_t bit_width(const uint64_t x) { return 64 - bit_ctzl(x); }
constexpr uint64_t bit_msb(const uint64_t x) { return x == 0 ? 0 : uint64_t(1) << (bit_width(x) - 1); }
constexpr uint64_t bit_lsb(const uint64_t x) { return x & (-x); }
constexpr uint64_t bit_cover(const uint64_t x) { return x == 0 ? 0 : bit_msb(2 * x - 1); }

constexpr uint64_t bit_rev(uint64_t x) {
  x = ((x >> 1) & 0x5555555555555555) | ((x & 0x5555555555555555) << 1);
  x = ((x >> 2) & 0x3333333333333333) | ((x & 0x3333333333333333) << 2);
  x = ((x >> 4) & 0x0F0F0F0F0F0F0F0F) | ((x & 0x0F0F0F0F0F0F0F0F) << 4);
  x = ((x >> 8) & 0x00FF00FF00FF00FF) | ((x & 0x00FF00FF00FF00FF) << 8);
  x = ((x >> 16) & 0x0000FFFF0000FFFF) | ((x & 0x0000FFFF0000FFFF) << 16);
  x = (x >> 32) | (x << 32);
  return x;
}

/**
 * @title Bit Operations
 */
#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/monoid.cpp"

#include <type_traits>
#line 5 "/Users/kodamankod/Desktop/cpp_programming/Library/other/monoid.cpp"
#include <stdexcept>

template <class T, class = void>
class has_identity: public std::false_type { };

template <class T>
class has_identity<T, typename std::conditional<false, decltype(T::identity()), void>::type>: public std::true_type { };

template <class T>
constexpr typename std::enable_if<has_identity<T>::value, typename T::type>::type empty_exception() {
  return T::identity();
}
template <class T>
[[noreturn]] typename std::enable_if<!has_identity<T>::value, typename T::type>::type empty_exception() {
  throw std::runtime_error("type T has no identity");
}

template <class T, bool HasIdentity>
class fixed_monoid_impl: public T {
public:
  using type = typename T::type;

  static constexpr type convert(const type &value) { return value; }
  static constexpr type revert(const type &value) { return value; }

  template <class Mapping, class Value, class... Args>
  static constexpr void operate(Mapping &&func, Value &value, const type &op, Args&&... args) {
    value = func(value, op, std::forward<Args>(args)...);
  }
  template <class Constraint>
  static constexpr bool satisfies(Constraint &&func, const type &value) {
    return func(value);
  }
};

template <class T>
class fixed_monoid_impl<T, false> {
public:
  class type {
  public:
    typename T::type value;
    bool state;
  
    explicit constexpr type(): value(typename T::type { }), state(false) { }
    explicit constexpr type(const typename T::type &value): value(value), state(true) { }
  };

  static constexpr type convert(const typename T::type &value) { return type(value); }
  static constexpr typename T::type revert(const type &value) { 
    if (!value.state) throw std::runtime_error("attempted to revert identity to non-monoid"); 
    return value.value; 
  }

  static constexpr type identity() { return type(); }
  static constexpr type operation(const type &v1, const type &v2) {
    if (!v1.state) return v2;
    if (!v2.state) return v1;
    return type(T::operation(v1.value, v2.value));
  }

  template <class Mapping, class Value, class... Args>
  static constexpr void operate(Mapping &&func, Value &value, const type &op, Args&&... args) {
    if (!op.state) return;
    value = func(value, op.value, std::forward<Args>(args)...);
  }
  template <class Constraint>
  static constexpr bool satisfies(Constraint &&func, const type &value) {
    if (!value.state) return false;
    return func(value.value);
  }
};

template <class T>
using fixed_monoid = fixed_monoid_impl<T, has_identity<T>::value>;

/**
 * @title Monoid Utility
 */
#line 5 "/Users/kodamankod/Desktop/cpp_programming/Library/container/lazy_propagation_segment_tree.cpp"

#line 8 "/Users/kodamankod/Desktop/cpp_programming/Library/container/lazy_propagation_segment_tree.cpp"
#include <iterator>
#line 11 "/Users/kodamankod/Desktop/cpp_programming/Library/container/lazy_propagation_segment_tree.cpp"

template <class CombinedMonoid>
class lazy_propagation_segment_tree {
public:
  using structure       = CombinedMonoid;
  using value_monoid    = typename CombinedMonoid::value_structure;
  using operator_monoid = typename CombinedMonoid::operator_structure;
  using value_type      = typename CombinedMonoid::value_structure::type;
  using operator_type   = typename CombinedMonoid::operator_structure::type;
  using size_type       = size_t;

private:
  using fixed_operator_monoid = fixed_monoid<operator_monoid>;
  using fixed_operator_type   = typename fixed_operator_monoid::type;

  class node_type {
  public:
    value_type    value;
    fixed_operator_type lazy;
    node_type(
      const value_type    &value = value_monoid::identity(),
      const fixed_operator_type &lazy = fixed_operator_monoid::identity()
    ): value(value), lazy(lazy) { }
  };

  static void S_apply(node_type &node, const fixed_operator_type &op, const size_type length) {
    fixed_operator_monoid::operate(structure::operation, node.value, op, length);
    node.lazy = fixed_operator_monoid::operation(node.lazy, op);
  }

  void M_propagate(const size_type index, const size_type length) {
    S_apply(M_tree[index << 1 | 0], M_tree[index].lazy, length);
    S_apply(M_tree[index << 1 | 1], M_tree[index].lazy, length);
    M_tree[index].lazy = fixed_operator_monoid::identity();
  }
  void M_fix_change(const size_type index) {
    M_tree[index].value = 
      value_monoid::operation(M_tree[index << 1 | 0].value, M_tree[index << 1 | 1].value);
  }

  void M_pushdown(const size_type index) {
    const size_type lsb = bit_ctzr(index);
    for (size_type story = bit_width(index); story != lsb; --story) {
      M_propagate(index >> story, 1 << (story - 1));
    }
  }
  void M_pullup(size_type index) {
    index >>= bit_ctzr(index);
    while (index != 1) {
      index >>= 1;
      M_fix_change(index);
    }
  }

  std::vector<node_type> M_tree;

public:
  lazy_propagation_segment_tree() = default;
  explicit lazy_propagation_segment_tree(const size_type size) { initialize(size); }
  template <class InputIterator>
  explicit lazy_propagation_segment_tree(InputIterator first, InputIterator last) { construct(first, last); }

  void initialize(const size_type size) {
    clear();
    M_tree.assign(size << 1, node_type());
  }

  template <class InputIterator>
  void construct(InputIterator first, InputIterator last) {
    clear();
    const size_type size = std::distance(first, last);
    M_tree.reserve(size << 1);
    M_tree.assign(size, node_type());
    for (; first != last; ++first) {
      M_tree.emplace_back(*first, fixed_operator_monoid::identity());
    }
    for (size_type index = size - 1; index != 0; --index) {
      M_fix_change(index);
    }
  }

  value_type fold(size_type first, size_type last) {
    assert(first <= last);
    assert(last <= size());
    first += size();
    last  += size();
    M_pushdown(first);
    M_pushdown(last);
    value_type fold_l = value_monoid::identity();
    value_type fold_r = value_monoid::identity();
    while (first != last) {
      if (first & 1) {
        fold_l = value_monoid::operation(fold_l, M_tree[first].value);
        ++first;
      }
      if (last & 1) {
        --last;
        fold_r = value_monoid::operation(M_tree[last].value, fold_r);
      }
      first >>= 1;
      last  >>= 1;
    }
    return value_monoid::operation(fold_l, fold_r);
  }

  void operate(size_type first, size_type last, const operator_type &op_) {
    assert(first <= last);
    assert(last <= size());
    const auto op = fixed_operator_monoid::convert(op_);
    first += size();
    last  += size();
    M_pushdown(first);
    M_pushdown(last);
    const size_type first_c = first;
    const size_type last_c  = last;
    for (size_type story = 0; first != last; ++story) {
      if (first & 1) {
        S_apply(M_tree[first], op, 1 << story);
        ++first;
      }
      if (last & 1) {
        --last;
        S_apply(M_tree[last], op, 1 << story);
      }
      first >>= 1;
      last  >>= 1;
    }
    M_pullup(first_c);
    M_pullup(last_c);
  }

  void assign(size_type index, const value_type &val) {
    assert(index < size());
    index += size();
    for (size_type story = bit_width(index); story != 0; --story) {
      M_propagate(index >> story, 1 << (story - 1));
    }
    M_tree[index].value = val;
    M_tree[index].lazy  = fixed_operator_monoid::identity();
    while (index != 1) {
      index >>= 1;
      M_fix_change(index);
    }
  }

  template <bool ToRight = true, class Constraint, std::enable_if_t<ToRight>* = nullptr> 
  size_type satisfies(const size_type left, Constraint &&func) {
    assert(left <= size());
    if (func(value_monoid::identity())) return left;
    size_type first = left + size();
    size_type last = 2 * size();
    M_pushdown(first);
    M_pushdown(last);
    const size_type last_c = last;
    value_type fold = value_monoid::identity();
    const auto try_merge = [&](const size_type index) {
      value_type tmp = value_monoid::operation(fold, M_tree[index].value);
      if (func(tmp)) return true;
      fold = std::move(tmp);
      return false;
    };
    const auto subtree = [&](size_type index, size_type story) {
      while (index < size()) {
        M_propagate(index, 1 << (story - 1));
        index <<= 1;
        if (!try_merge(index)) ++index;
        --story;
      }
      return index - size() + 1;
    };
    size_type story = 0;
    while (first < last) {
      if (first & 1) {
        if (try_merge(first)) return subtree(first, story);
        ++first;
      }
      first >>= 1;
      last >>= 1;
      ++story;
    }
    while (story--) {
      last = last_c >> story;
      if (last & 1) {
        --last;
        if (try_merge(last)) return subtree(last, story);
      }
    }
    return size() + 1;
  }

  template <bool ToRight = true, class Constraint, std::enable_if_t<!ToRight>* = nullptr> 
  size_type satisfies(const size_type right, Constraint &&func) {
    assert(right <= size());
    if (func(value_monoid::identity())) return right;
    size_type first = size();
    size_type last = right + size();
    M_pushdown(first);
    M_pushdown(last);
    const size_type first_c = first;
    value_type fold = value_monoid::identity();
    const auto try_merge = [&](const size_type index) {
      value_type tmp = value_monoid::operation(M_tree[index].value, fold);
      if (func(tmp)) return true;
      fold = std::move(tmp);
      return false;
    };
    const auto subtree = [&](size_type index, size_type story) {
      while (index < size()) {
        M_propagate(index, 1 << (story - 1));
        index <<= 1;
        if (try_merge(index + 1)) ++index;
        --story;
      }
      return index - size();
    };
    size_type story = 0;
    while (first < last) {
      if (first & 1) ++first;
      if (last & 1) {
        --last;
        if (try_merge(last)) return subtree(last, story);
      }
      first >>= 1;
      last >>= 1;
      ++story;
    }
    const size_type cover = bit_cover(first_c);
    while (story--) {
      first = (cover >> story) - ((cover - first_c) >> story);
      if (first & 1) {
        if (try_merge(first)) return subtree(first, story);
      }
    }
    return size_type(-1);
  }

  void clear() {
    M_tree.clear();
    M_tree.shrink_to_fit();
  }
  size_type size() const { 
    return M_tree.size() >> 1;
  }
};

/**
 * @title Lazy Propagation Segment Tree
 */
#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/fast_io.cpp"

#line 5 "/Users/kodamankod/Desktop/cpp_programming/Library/other/fast_io.cpp"
#include <cstring>
#line 7 "/Users/kodamankod/Desktop/cpp_programming/Library/other/fast_io.cpp"

namespace fast_io {
  static constexpr size_t buf_size = 1 << 18;
  static constexpr size_t buf_margin = 1;
  static constexpr size_t block_size = 10000;
  static constexpr size_t integer_size = 20;

  static char inbuf[buf_size + buf_margin] = {};
  static char outbuf[buf_size + buf_margin] = {};
  static char block_str[block_size * 4 + buf_margin] = {};

  static constexpr uint64_t power10[] = {
    1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,
    1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000,
    100000000000000, 1000000000000000, 10000000000000000, 100000000000000000,
    1000000000000000000, 10000000000000000000u
  };

  class scanner {
  private:
    size_t M_in_pos = 0, M_in_end = buf_size;

    void M_load() { 
      M_in_end = fread(inbuf, 1, buf_size, stdin); 
      inbuf[M_in_end] = '\0';  
    }
    void M_reload() {
      size_t length = M_in_end - M_in_pos;
      memmove(inbuf, inbuf + M_in_pos, length);
      M_in_end = length + fread(inbuf + length, 1, buf_size - length, stdin);
      inbuf[M_in_end] = '\0';
      M_in_pos = 0;
    }

    void M_ignore_space() {
      while (inbuf[M_in_pos] <= ' ') {
        if (__builtin_expect(++M_in_pos == M_in_end, 0)) M_reload();
      }
    }

    char M_next() { return inbuf[M_in_pos++]; }
    char M_next_nonspace() {
      M_ignore_space();
      return inbuf[M_in_pos++];
    }

  public:
    scanner() { M_load(); }
    
    void scan(char &c) { c = M_next_nonspace(); }
    void scan(std::string &s) {
      M_ignore_space();
      s = "";
      do {
        size_t start = M_in_pos;
        while (inbuf[M_in_pos] > ' ') ++M_in_pos;
        s += std::string(inbuf + start, inbuf + M_in_pos);
        if (inbuf[M_in_pos] != '\0') break;
        M_reload();
      } while (true);
    }

    template <class T>
    typename std::enable_if<std::is_integral<T>::value, void>::type scan(T &x) {
      char c = M_next_nonspace();
      if (__builtin_expect(M_in_pos + integer_size >= M_in_end, 0)) M_reload();
      bool n = false;
      if (c == '-') n = true, x = 0;
      else x = c & 15;
      while ((c = M_next()) >= '0') x = x * 10 + (c & 15);
      if (n) x = -x;
    }

    template <class T, class... Args>
    void scan(T &x, Args&... args) {
      scan(x); scan(args...);
    }

    template <class T>
    scanner& operator >> (T &x) {
      scan(x); return *this;
    }

  };

  class printer {
  private:
    size_t M_out_pos = 0;

    void M_flush() {
      fwrite(outbuf, 1, M_out_pos, stdout);
      M_out_pos = 0;
    }

    void M_precompute() {
      for (size_t i = 0; i < block_size; ++i) {
        size_t j = 4, k = i;
        while (j--) {
          block_str[i * 4 + j] = k % 10 + '0';
          k /= 10;
        }
      }
    }

    static constexpr size_t S_integer_digits(uint64_t n) {
      if (n >= power10[10]) {
        if (n >= power10[19]) return 20;
        if (n >= power10[18]) return 19;
        if (n >= power10[17]) return 18;
        if (n >= power10[16]) return 17;
        if (n >= power10[15]) return 16;
        if (n >= power10[14]) return 15;
        if (n >= power10[13]) return 14;
        if (n >= power10[12]) return 13;
        if (n >= power10[11]) return 12;
        return 11;
      }
      else {
        if (n >= power10[9]) return 10;
        if (n >= power10[8]) return 9;
        if (n >= power10[7]) return 8;
        if (n >= power10[6]) return 7;
        if (n >= power10[5]) return 6;
        if (n >= power10[4]) return 5;
        if (n >= power10[3]) return 4;
        if (n >= power10[2]) return 3;
        if (n >= power10[1]) return 2;
        return 1;
      }
    }

  public:
    printer() { M_precompute(); }
    ~printer() { M_flush(); }

    void print(char c) { 
      outbuf[M_out_pos++] = c;
      if (__builtin_expect(M_out_pos == buf_size, 0)) M_flush();
    }
    void print(const char *s) {
      while (*s != 0) {
        outbuf[M_out_pos++] = *s++;
        if (M_out_pos == buf_size) M_flush();
      }
    }
    void print(const std::string &s) {
      for (auto c: s) {
        outbuf[M_out_pos++] = c;
        if (M_out_pos == buf_size) M_flush();
      }
    }
    
    template <class T>
    typename std::enable_if<std::is_integral<T>::value, void>::type print(T x) {
      if (__builtin_expect(M_out_pos + integer_size >= buf_size, 0)) M_flush();
      if (x < 0) print('-'), x = -x;
      size_t digit = S_integer_digits(x);
      size_t len = digit;
      while (len >= 4) {
        len -= 4;
        memcpy(outbuf + M_out_pos + len, block_str + (x % block_size) * 4, 4);
        x /= 10000;
      }
      memcpy(outbuf + M_out_pos, block_str + x * 4 + 4 - len, len);
      M_out_pos += digit;
    }

    template <class T, class... Args>
    void print(const T &x, const Args&... args) {
      print(x); print(' '); print(args...);
    }

    template <class... Args>
    void println(const Args&... args) {
      print(args...); print('\n');
    }

    template <class T>
    printer& operator << (const T &x) {
      print(x); return *this;
    }

  };

};

/**
 * @title Fast Input/Output
 */
#line 17 "main.cpp"

template <class T>
using Vec = std::vector<T>;

struct lst_monoid {
  struct value_structure {
    using type = long long;
    static type identity() { return 0; }
    static type operation(const type& v1, const type& v2) { 
      return v1 + v2;
    }
  };
  struct operator_structure {
    using type = long long;
    static type identity() { return 0; }
    static type operation(const type& v1, const type& v2) { 
      return v1 + v2;
    }
  };
  static typename value_structure::type operation(
    const typename value_structure::type    &val,
    const typename operator_structure::type &op,
    const size_t length = 1) {
    return val + op * (long long) length;
  }
};

fast_io::scanner cin;
fast_io::printer cout;

template <class T>
T scan() {
  T x;
  cin.scan(x);
  return x;
}

int S[200000];
int left[200000];
int right[200000];
Vec<std::pair<int, int>> add1[200000];
Vec<std::pair<int, int>> add2[200000];
Vec<int> query[200000];
long long ans[200000];

int main() {
  const auto N = scan<int>();
  const auto Q = scan<int>();
  for (int i = 0; i < N; ++i) {
    S[i] = scan<int>();
  }
  {
    std::stack<std::pair<int, int>> st;
    st.emplace(1000000005, 0);
    for (int i = 0; i < N; ++i) {
      while (st.top().first < S[i]) {
        st.pop();
      }
      left[i] = st.top().second;
      st.emplace(S[i], i + N);
    }
  }
  {
    std::stack<std::pair<int, int>> st;
    st.emplace(1000000005, 2 * N);
    for (int i = N - 1; i >= 0; --i) {
      while (st.top().first <= S[i]) {
        st.pop();
      }
      right[i] = st.top().second;
      st.emplace(S[i], i + N);
    }
  }
  Vec<int> T(Q), L(Q), R(Q);
  for (int i = 0; i < Q; ++i) {
    T[i] = std::min(scan<int>(), N - 1);
    L[i] = scan<int>() + N - 1;
    R[i] = scan<int>() + N;
  }
  const auto add_triangle = [&](const int l, const int r, const int x) {
    add1[0].emplace_back(l, x);
    add2[0].emplace_back(r, -x);
    const auto t = r - l;
    if (t < N) {
      add1[t].emplace_back(l, -x);
      add2[t].emplace_back(r, x);
    }
  };
  for (int i = 0; i < N; ++i) {
    add_triangle(left[i] + 1, right[i], S[i]);
    add_triangle(left[i] + 1, i + N, -S[i]);
    add_triangle(i + N + 1, right[i], -S[i]);
  }
  for (int i = 0; i < Q; ++i) {
    query[T[i]].emplace_back(i);
  }
  lazy_propagation_segment_tree<lst_monoid> seg1(2 * N), seg2(2 * N);
  Vec<long long> ans(Q);
  for (int i = 0; i < N; ++i) {
    for (const auto [l, x]: add1[i]) {
      seg1.operate(l, 2 * N, x);
    }
    for (const auto [l, x]: add2[i]) {
      seg2.operate(l, 2 * N, x);
    }
    for (const auto k: query[i]) {
      ans[k] += seg1.fold(L[k] - i, R[k] - i);
      ans[k] += seg2.fold(L[k], R[k]);
    }
  }
  for (int i = 0; i < Q; ++i) {
    cout.println(ans[i]);
  }
  return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	14444 KB	Output is correct
2	Correct	11 ms	14572 KB	Output is correct
3	Correct	11 ms	14572 KB	Output is correct
4	Correct	11 ms	14572 KB	Output is correct
5	Correct	11 ms	14572 KB	Output is correct
6	Correct	11 ms	14572 KB	Output is correct
7	Correct	11 ms	14572 KB	Output is correct
8	Correct	11 ms	14572 KB	Output is correct
9	Correct	11 ms	14572 KB	Output is correct
10	Correct	11 ms	14572 KB	Output is correct
11	Correct	11 ms	14700 KB	Output is correct
12	Correct	10 ms	14572 KB	Output is correct
13	Correct	11 ms	14572 KB	Output is correct
14	Correct	11 ms	14572 KB	Output is correct
15	Correct	11 ms	14572 KB	Output is correct
16	Correct	11 ms	14572 KB	Output is correct
17	Correct	11 ms	14572 KB	Output is correct
18	Correct	11 ms	14572 KB	Output is correct
19	Correct	11 ms	14572 KB	Output is correct
20	Correct	12 ms	14572 KB	Output is correct
21	Correct	11 ms	14572 KB	Output is correct
22	Correct	11 ms	14572 KB	Output is correct
23	Correct	11 ms	14572 KB	Output is correct
24	Correct	11 ms	14572 KB	Output is correct
25	Correct	11 ms	14592 KB	Output is correct
26	Correct	11 ms	14572 KB	Output is correct
27	Correct	12 ms	14572 KB	Output is correct
28	Correct	11 ms	14572 KB	Output is correct
29	Correct	11 ms	14572 KB	Output is correct
30	Correct	11 ms	14572 KB	Output is correct
31	Correct	11 ms	14572 KB	Output is correct
32	Correct	11 ms	14700 KB	Output is correct

Subtask #2

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	14444 KB	Output is correct
2	Correct	960 ms	69192 KB	Output is correct
3	Correct	868 ms	74984 KB	Output is correct
4	Correct	916 ms	75384 KB	Output is correct
5	Correct	990 ms	76808 KB	Output is correct
6	Correct	976 ms	74864 KB	Output is correct
7	Correct	932 ms	75436 KB	Output is correct
8	Correct	999 ms	77176 KB	Output is correct
9	Execution timed out	1061 ms	75764 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-

Subtask #3

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	14444 KB	Output is correct
2	Correct	976 ms	70524 KB	Output is correct
3	Correct	977 ms	75132 KB	Output is correct
4	Correct	973 ms	78356 KB	Output is correct
5	Correct	980 ms	75644 KB	Output is correct
6	Execution timed out	1010 ms	76148 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #4

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1062 ms	71424 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	14444 KB	Output is correct
2	Correct	11 ms	14572 KB	Output is correct
3	Correct	11 ms	14572 KB	Output is correct
4	Correct	11 ms	14572 KB	Output is correct
5	Correct	11 ms	14572 KB	Output is correct
6	Correct	11 ms	14572 KB	Output is correct
7	Correct	11 ms	14572 KB	Output is correct
8	Correct	11 ms	14572 KB	Output is correct
9	Correct	11 ms	14572 KB	Output is correct
10	Correct	11 ms	14572 KB	Output is correct
11	Correct	11 ms	14700 KB	Output is correct
12	Correct	10 ms	14572 KB	Output is correct
13	Correct	11 ms	14572 KB	Output is correct
14	Correct	11 ms	14572 KB	Output is correct
15	Correct	11 ms	14572 KB	Output is correct
16	Correct	11 ms	14572 KB	Output is correct
17	Correct	11 ms	14572 KB	Output is correct
18	Correct	11 ms	14572 KB	Output is correct
19	Correct	11 ms	14572 KB	Output is correct
20	Correct	12 ms	14572 KB	Output is correct
21	Correct	11 ms	14572 KB	Output is correct
22	Correct	11 ms	14572 KB	Output is correct
23	Correct	11 ms	14572 KB	Output is correct
24	Correct	11 ms	14572 KB	Output is correct
25	Correct	11 ms	14592 KB	Output is correct
26	Correct	11 ms	14572 KB	Output is correct
27	Correct	12 ms	14572 KB	Output is correct
28	Correct	11 ms	14572 KB	Output is correct
29	Correct	11 ms	14572 KB	Output is correct
30	Correct	11 ms	14572 KB	Output is correct
31	Correct	11 ms	14572 KB	Output is correct
32	Correct	11 ms	14700 KB	Output is correct
33	Correct	960 ms	69192 KB	Output is correct
34	Correct	868 ms	74984 KB	Output is correct
35	Correct	916 ms	75384 KB	Output is correct
36	Correct	990 ms	76808 KB	Output is correct
37	Correct	976 ms	74864 KB	Output is correct
38	Correct	932 ms	75436 KB	Output is correct
39	Correct	999 ms	77176 KB	Output is correct
40	Execution timed out	1061 ms	75764 KB	Time limit exceeded
41	Halted	0 ms	0 KB	-