oj.uz

Submission #625926

# Submission time Handle Problem Language Result Execution time Memory
625926 2022-08-11T03:05:53 Z Benq Radio Towers (IOI22_towers) C++17
100 / 100
 1762 ms 256916 KB 
#include "towers.h"

#include <vector>

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python! 

// pairs
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define mp make_pair
#define f first
#define s second

#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;

// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

#define lb lower_bound
#define ub upper_bound
tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }
tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }

// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll BIG = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;

// bitwise ops
// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until USACO updates ...
  return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x)) 
constexpr int p2(int x) { return 1<<x; }
constexpr int msk2(int x) { return p2(x)-1; }

ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

tcT> bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0; } // set a = max(a,b)

tcTU> T fstTrue(T lo, T hi, U f) {
  ++hi; assert(lo <= hi); // assuming f is increasing
  while (lo < hi) { // find first index such that f is true 
    T mid = lo+(hi-lo)/2;
    f(mid) ? hi = mid : lo = mid+1; 
  } 
  return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
  --lo; assert(lo <= hi); // assuming f is decreasing
  while (lo < hi) { // find first index such that f is true 
    T mid = lo+(hi-lo+1)/2;
    f(mid) ? lo = mid : hi = mid-1;
  } 
  return lo;
}
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
  sort(all(v)); v.erase(unique(all(v)),end(v)); }
tcTU> void erase(T& t, const U& u) { // don't erase
  auto it = t.find(u); assert(it != end(t));
  t.erase(it); } // element that doesn't exist from (multi)set

#define tcTUU tcT, class ...U

inline namespace Helpers {
  //////////// is_iterable
  // https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable
  // this gets used only when we can call begin() and end() on that type
  tcT, class = void> struct is_iterable : false_type {};
  tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
                                    decltype(end(declval<T>()))
                                   >
                         > : true_type {};
  tcT> constexpr bool is_iterable_v = is_iterable<T>::value;

  //////////// is_readable
  tcT, class = void> struct is_readable : false_type {};
  tcT> struct is_readable<T,
          typename std::enable_if_t<
              is_same_v<decltype(cin >> declval<T&>()), istream&>
          >
      > : true_type {};
  tcT> constexpr bool is_readable_v = is_readable<T>::value;

  //////////// is_printable
  // // https://nafe.es/posts/2020-02-29-is-printable/
  tcT, class = void> struct is_printable : false_type {};
  tcT> struct is_printable<T,
          typename std::enable_if_t<
              is_same_v<decltype(cout << declval<T>()), ostream&>
          >
      > : true_type {};
  tcT> constexpr bool is_printable_v = is_printable<T>::value;
}

inline namespace Input {
  tcT> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
  tcTUU> void re(T& t, U&... u);
  tcTU> void re(pair<T,U>& p); // pairs

  // re: read
  tcT> typename enable_if<is_readable_v<T>,void>::type re(T& x) { cin >> x; } // default
  tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; } // complex
  tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i); // ex. vectors, arrays
  tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
  tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i) {
    each(x,i) re(x); }
  tcTUU> void re(T& t, U&... u) { re(t); re(u...); } // read multiple

  // rv: resize and read vectors
  void rv(size_t) {}
  tcTUU> void rv(size_t N, V<T>& t, U&... u);
  template<class...U> void rv(size_t, size_t N2, U&... u);
  tcTUU> void rv(size_t N, V<T>& t, U&... u) {
    t.rsz(N); re(t);
    rv(N,u...); }
  template<class...U> void rv(size_t, size_t N2, U&... u) {
    rv(N2,u...); }

  // dumb shortcuts to read in ints
  void decrement() {} // subtract one from each
  tcTUU> void decrement(T& t, U&... u) { --t; decrement(u...); }
  #define ints(...) int __VA_ARGS__; re(__VA_ARGS__);
  #define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__);
}

inline namespace ToString {
  tcT> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;

  // ts: string representation to print
  tcT> typename enable_if<is_printable_v<T>,str>::type ts(T v) {
    stringstream ss; ss << fixed << setprecision(15) << v;
    return ss.str(); } // default
  tcT> str bit_vec(T t) { // bit vector to string
    str res = "{"; F0R(i,sz(t)) res += ts(t[i]);
    res += "}"; return res; }
  str ts(V<bool> v) { return bit_vec(v); }
  template<size_t SZ> str ts(bitset<SZ> b) { return bit_vec(b); } // bit vector
  tcTU> str ts(pair<T,U> p); // pairs
  tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v); // vectors, arrays
  tcTU> str ts(pair<T,U> p) { return "("+ts(p.f)+", "+ts(p.s)+")"; }
  tcT> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep) {
    // convert container to string w/ separator sep
    bool fst = 1; str res = "";
    for (const auto& x: v) {
      if (!fst) res += sep;
      fst = 0; res += ts(x);
    }
    return res;
  }
  tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v) {
    return "{"+ts_sep(v,", ")+"}"; }

  // for nested DS
  template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type 
    ts_lev(const T& v) { return {ts(v)}; }
  template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type 
    ts_lev(const T& v) {
    if (lev == 0 || !sz(v)) return {ts(v)};
    vs res;
    for (const auto& t: v) {
      if (sz(res)) res.bk += ",";
      vs tmp = ts_lev<lev-1>(t);
      res.ins(end(res),all(tmp));
    }
    F0R(i,sz(res)) {
      str bef = " "; if (i == 0) bef = "{";
      res[i] = bef+res[i];
    }
    res.bk += "}";
    return res;
  }
}

inline namespace Output {
  template<class T> void pr_sep(ostream& os, str, const T& t) { os << ts(t); }
  template<class T, class... U> void pr_sep(ostream& os, str sep, const T& t, const U&... u) {
    pr_sep(os,sep,t); os << sep; pr_sep(os,sep,u...); }
  // print w/ no spaces
  template<class ...T> void pr(const T&... t) { pr_sep(cout,"",t...); } 
  // print w/ spaces, end with newline
  void ps() { cout << "\n"; }
  template<class ...T> void ps(const T&... t) { pr_sep(cout," ",t...); ps(); } 
  // debug to cerr
  template<class ...T> void dbg_out(const T&... t) {
    pr_sep(cerr," | ",t...); cerr << endl; }
  void loc_info(int line, str names) {
    cerr << "Line(" << line << ") -> [" << names << "]: "; }
  template<int lev, class T> void dbgl_out(const T& t) {
    cerr << "\n\n" << ts_sep(ts_lev<lev>(t),"\n") << "\n" << endl; }
  #ifdef LOCAL
    #define dbg(...) loc_info(__LINE__,#__VA_ARGS__), dbg_out(__VA_ARGS__)
    #define dbgl(lev,x) loc_info(__LINE__,#x), dbgl_out<lev>(x)
  #else // don't actually submit with this
    #define dbg(...) 0
    #define dbgl(lev,x) 0
  #endif

  const clock_t beg = clock();
  #define dbg_time() dbg((db)(clock()-beg)/CLOCKS_PER_SEC)
}

inline namespace FileIO {
  void setIn(str s)  { freopen(s.c_str(),"r",stdin); }
  void setOut(str s) { freopen(s.c_str(),"w",stdout); }
  void setIO(str s = "") {
    cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams
    // cin.exceptions(cin.failbit);
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s)) setIn(s+".in"), setOut(s+".out"); // for old USACO
  }
}

/**
 * Description: 1D range minimum query. Can also do queries 
   * for any associative operation in $O(1)$ with D\&C
 * Source: KACTL
 * Verification: 
  * https://cses.fi/problemset/stats/1647/
  * http://wcipeg.com/problem/ioi1223
  * https://pastebin.com/ChpniVZL
 * Memory: O(N\log N)
 * Time: O(1)
 */

tcT> struct RMQ {
  int level(int x) { return 31-__builtin_clz(x); }
  V<vi> jmp;
  void init(const V<T>& _v) {
    jmp = {_v};
    for (int j = 1; 1<<j <= sz(_v); ++j) {
      jmp.pb(vi(sz(_v)-(1<<j)+1));
      F0R(i,sz(jmp[j])) jmp[j][i] = min(jmp[j-1][i],
        jmp[j-1][i+(1<<(j-1))]);
    }
  }
  int query(int l, int r) {
    assert(l <= r); int d = level(r-l+1);
    return min(jmp[d][l],jmp[d][r-(1<<d)+1]); }
};

struct PSeg {
  // Either globally or in a single class:
  static char buf[450 << 20];
  void* operator new(size_t s) {
    static size_t i = sizeof buf;
    assert(s < i);
    return (void*)&buf[i -= s];
  }
  void operator delete(void*) {}

  int N;
  struct Node {
    int sum = 0;
    Node *l = nullptr, *r = nullptr;
    Node* upd(int L, int R, int pos, int inc) {
      if (L == R) {
        return new Node{this->sum+inc};
      }
      int M = (L+R)/2;
      if (pos <= M) {
        auto l = this->l->upd(L, M, pos, inc);
        return new Node{l->sum+this->r->sum, l, this->r};
      } else {
        auto r = this->r->upd(M+1, R, pos, inc);
        return new Node{this->l->sum+r->sum, this->l, r};
      }
    }
    int query(int L, int R, int up) {
      if (R <= up) return sum;
      if (up < L) return 0;
      int M = (L+R)/2;
      return l->query(L, M, up) + r->query(M+1, R, up);
    }
  };
  V<Node*> stor;
  Node* build(int L, int R) {
    if (L == R) return new Node{};
    int M = (L+R)/2;
    auto l = build(L, M), r = build(M+1, R);
    return new Node{0,l,r};
  }
  void inc(int pos, int inc) {
    stor.pb(stor.bk->upd(0, N-1, pos, inc));
  }
  int query(int it, int up) {
    return stor.at(it)->query(0, N-1, up);
  }
  void init(int N_) {
    N = N_;
    stor.pb(build(0, N-1));
  }
};


RMQ<int> pos, neg;
vi H, lef, rig;

int qmin(int l, int r) {
  return pos.query(l, r);
}

int qmax(int l, int r) {
  return -neg.query(l, r);
}

V<AR<int,4>> ev;
PSeg a, b;

void init(int N, std::vector<int> H_) {
  H = H_;
  pos.init(H_);
  each(t,H_) t *= -1;
  neg.init(H_);
  lef.rsz(N), rig.rsz(N);
  {
    vi stk{-1};
    F0R(i,N) {
      while (stk.bk != -1 && H[stk.bk] <= H[i]) stk.pop_back();
      lef[i] = stk.bk+1;
      stk.pb(i);
    }
  }
  {
    vi stk{N};
    R0F(i,N) {
      while (stk.bk != N && H[stk.bk] < H[i]) stk.pop_back();
      rig[i] = stk.bk-1;
      stk.pb(i);
    }
  }
  F0R(i,N) if (lef[i] < i) {
    int mn = qmin(lef[i], i);
    int lo = qmax(lef[i], i-1), hi = H[i];
    lo -= mn, hi -= mn;
    assert(lo <= hi);
    if (lo < hi) {
      // dbg("PUSHING L", lef[i], i, lo, hi);
      ev.pb({lo, 1, lef[i], i});
      ev.pb({hi, 0, lef[i], i});
    }
  }
  F0R(i,N) if (rig[i] > i) {
    int mn = qmin(i, rig[i]);
    int lo = qmax(i+1, rig[i]), hi = H[i];
    lo -= mn, hi -= mn;
    assert(lo <= hi);
    if (lo < hi) {
      // dbg("PUSHING R", i, rig[i], lo, hi);
      ev.pb({lo, 1, i, rig[i]});
      ev.pb({hi, 0, i, rig[i]});
    }
  }
  sor(ev);
  a.init(N), b.init(N);
  each(t, ev) {
    a.inc(t[2], (t[1] == 1 ? 1 : -1));
    b.inc(t[3], (t[1] == 1 ? 1 : -1));
  }
}
// # with right <= R - # with

int max_towers(int L, int R, int D) {
  // dbg("MAX TOWERS", L, R, D);
  auto small_interval = [&](int l, int r) {
    // dbg("TESTING", l, r);
    return l <= r && qmax(l, r) - qmin(l, r) < D;
  };
  if (small_interval(L, R)) return 1;
  int ans = 0;
  {
    int M = fstTrue(L, R, [&](int i) { return qmax(L, i) - qmin(L, i) >= D; } );
    if (M <= R && lef.at(M) < L) ++ans;
  }
  {
    int M = lstTrue(L, R, [&](int i) { return qmax(i, R) - qmin(i, R) >= D; });
    if (M >= L && rig.at(M) > R) ++ans;
  }
  // dbg(ev, L, R, D);
  // dbg("BEFORE", ans);
  int it = lwb(ev, {D, 0, 0, 0});
  ans += b.query(it, R) - a.query(it, L-1);
  return ans;
}

Compilation message

towers.cpp: In function 'void FileIO::setIn(str)':
towers.cpp:248:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  248 |   void setIn(str s)  { freopen(s.c_str(),"r",stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
towers.cpp: In function 'void FileIO::setOut(str)':
towers.cpp:249:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  249 |   void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 145516 KB Output is correct
2 Correct 1192 ms 256404 KB Output is correct
3 Correct 1304 ms 256444 KB Output is correct
4 Correct 1276 ms 256776 KB Output is correct
5 Correct 1176 ms 250556 KB Output is correct
6 Correct 1452 ms 256672 KB Output is correct
7 Correct 1592 ms 250560 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 7 ms 3664 KB Output is correct
10 Correct 6 ms 3664 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 848 KB Output is correct
2 Correct 8 ms 3792 KB Output is correct
3 Correct 7 ms 3792 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 6 ms 3792 KB Output is correct
6 Correct 7 ms 3748 KB Output is correct
7 Correct 6 ms 3792 KB Output is correct
8 Correct 5 ms 3792 KB Output is correct
9 Correct 6 ms 3712 KB Output is correct
10 Correct 5 ms 3792 KB Output is correct
11 Correct 5 ms 3792 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 8 ms 3712 KB Output is correct
14 Correct 5 ms 3664 KB Output is correct
15 Correct 6 ms 3860 KB Output is correct
16 Correct 5 ms 3804 KB Output is correct
17 Correct 6 ms 3792 KB Output is correct
18 Correct 5 ms 3664 KB Output is correct
19 Correct 5 ms 3792 KB Output is correct
20 Correct 5 ms 3784 KB Output is correct
21 Correct 5 ms 3792 KB Output is correct
22 Correct 7 ms 3816 KB Output is correct
23 Correct 6 ms 3704 KB Output is correct
24 Correct 5 ms 3792 KB Output is correct
25 Correct 2 ms 1736 KB Output is correct
26 Correct 9 ms 3760 KB Output is correct
27 Correct 6 ms 3792 KB Output is correct
28 Correct 6 ms 3792 KB Output is correct
29 Correct 5 ms 3792 KB Output is correct
30 Correct 5 ms 3792 KB Output is correct
31 Correct 6 ms 3812 KB Output is correct
32 Correct 6 ms 3792 KB Output is correct
33 Correct 4 ms 3664 KB Output is correct
34 Correct 6 ms 3792 KB Output is correct
35 Correct 7 ms 3792 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 848 KB Output is correct
2 Correct 8 ms 3792 KB Output is correct
3 Correct 7 ms 3792 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 6 ms 3792 KB Output is correct
6 Correct 7 ms 3748 KB Output is correct
7 Correct 6 ms 3792 KB Output is correct
8 Correct 5 ms 3792 KB Output is correct
9 Correct 6 ms 3712 KB Output is correct
10 Correct 5 ms 3792 KB Output is correct
11 Correct 5 ms 3792 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 8 ms 3712 KB Output is correct
14 Correct 5 ms 3664 KB Output is correct
15 Correct 6 ms 3860 KB Output is correct
16 Correct 5 ms 3804 KB Output is correct
17 Correct 6 ms 3792 KB Output is correct
18 Correct 5 ms 3664 KB Output is correct
19 Correct 5 ms 3792 KB Output is correct
20 Correct 5 ms 3784 KB Output is correct
21 Correct 5 ms 3792 KB Output is correct
22 Correct 7 ms 3816 KB Output is correct
23 Correct 6 ms 3704 KB Output is correct
24 Correct 5 ms 3792 KB Output is correct
25 Correct 2 ms 1736 KB Output is correct
26 Correct 9 ms 3760 KB Output is correct
27 Correct 6 ms 3792 KB Output is correct
28 Correct 6 ms 3792 KB Output is correct
29 Correct 5 ms 3792 KB Output is correct
30 Correct 5 ms 3792 KB Output is correct
31 Correct 6 ms 3812 KB Output is correct
32 Correct 6 ms 3792 KB Output is correct
33 Correct 4 ms 3664 KB Output is correct
34 Correct 6 ms 3792 KB Output is correct
35 Correct 7 ms 3792 KB Output is correct
36 Correct 374 ms 159896 KB Output is correct
37 Correct 465 ms 254784 KB Output is correct
38 Correct 449 ms 254976 KB Output is correct
39 Correct 516 ms 254832 KB Output is correct
40 Correct 504 ms 254820 KB Output is correct
41 Correct 503 ms 254848 KB Output is correct
42 Correct 430 ms 254768 KB Output is correct
43 Correct 303 ms 256740 KB Output is correct
44 Correct 315 ms 250568 KB Output is correct
45 Correct 340 ms 254088 KB Output is correct
46 Correct 299 ms 250536 KB Output is correct
47 Correct 476 ms 254868 KB Output is correct
48 Correct 463 ms 254852 KB Output is correct
49 Correct 459 ms 254768 KB Output is correct
50 Correct 391 ms 250528 KB Output is correct
51 Correct 339 ms 256700 KB Output is correct
52 Correct 458 ms 254888 KB Output is correct
53 Correct 554 ms 254880 KB Output is correct
54 Correct 501 ms 254808 KB Output is correct
55 Correct 304 ms 250468 KB Output is correct
56 Correct 331 ms 256916 KB Output is correct
57 Correct 489 ms 245620 KB Output is correct
58 Correct 458 ms 254884 KB Output is correct
59 Correct 464 ms 254892 KB Output is correct
60 Correct 453 ms 254864 KB Output is correct
61 Correct 447 ms 254864 KB Output is correct
62 Correct 461 ms 254924 KB Output is correct
63 Correct 434 ms 254944 KB Output is correct
64 Correct 291 ms 256816 KB Output is correct
65 Correct 295 ms 250648 KB Output is correct
66 Correct 320 ms 256820 KB Output is correct
67 Correct 290 ms 250524 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1342 ms 252984 KB Output is correct
2 Correct 1504 ms 254852 KB Output is correct
3 Correct 1578 ms 254920 KB Output is correct
4 Correct 1561 ms 254876 KB Output is correct
5 Correct 1487 ms 254964 KB Output is correct
6 Correct 1532 ms 254788 KB Output is correct
7 Correct 1634 ms 254884 KB Output is correct
8 Correct 1422 ms 256804 KB Output is correct
9 Correct 1388 ms 250524 KB Output is correct
10 Correct 1398 ms 254856 KB Output is correct
11 Correct 1410 ms 253676 KB Output is correct
12 Correct 1419 ms 256768 KB Output is correct
13 Correct 1389 ms 250516 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 5 ms 3664 KB Output is correct
16 Correct 5 ms 3664 KB Output is correct
17 Correct 456 ms 254804 KB Output is correct
18 Correct 427 ms 254852 KB Output is correct
19 Correct 429 ms 254896 KB Output is correct
20 Correct 278 ms 250568 KB Output is correct
21 Correct 302 ms 256652 KB Output is correct
22 Correct 437 ms 254768 KB Output is correct
23 Correct 489 ms 254884 KB Output is correct
24 Correct 452 ms 254772 KB Output is correct
25 Correct 307 ms 250604 KB Output is correct
26 Correct 333 ms 256680 KB Output is correct
27 Correct 5 ms 3920 KB Output is correct
28 Correct 5 ms 3792 KB Output is correct
29 Correct 6 ms 3764 KB Output is correct
30 Correct 5 ms 3740 KB Output is correct
31 Correct 6 ms 3792 KB Output is correct
32 Correct 5 ms 3792 KB Output is correct
33 Correct 6 ms 3792 KB Output is correct
34 Correct 5 ms 3792 KB Output is correct
35 Correct 6 ms 3664 KB Output is correct
36 Correct 6 ms 3848 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 54488 KB Output is correct
2 Correct 1397 ms 254992 KB Output is correct
3 Correct 1423 ms 254820 KB Output is correct
4 Correct 1389 ms 254900 KB Output is correct
5 Correct 1402 ms 254904 KB Output is correct
6 Correct 1406 ms 254932 KB Output is correct
7 Correct 1351 ms 254864 KB Output is correct
8 Correct 1293 ms 256828 KB Output is correct
9 Correct 1406 ms 250460 KB Output is correct
10 Correct 1190 ms 256720 KB Output is correct
11 Correct 1128 ms 252096 KB Output is correct
12 Correct 464 ms 254836 KB Output is correct
13 Correct 441 ms 254896 KB Output is correct
14 Correct 446 ms 254900 KB Output is correct
15 Correct 286 ms 250588 KB Output is correct
16 Correct 306 ms 256828 KB Output is correct
17 Correct 424 ms 245720 KB Output is correct
18 Correct 444 ms 254928 KB Output is correct
19 Correct 433 ms 254772 KB Output is correct
20 Correct 453 ms 254872 KB Output is correct
21 Correct 440 ms 254812 KB Output is correct
22 Correct 444 ms 254768 KB Output is correct
23 Correct 459 ms 254932 KB Output is correct
24 Correct 306 ms 256808 KB Output is correct
25 Correct 321 ms 250552 KB Output is correct
26 Correct 303 ms 256856 KB Output is correct
27 Correct 300 ms 250512 KB Output is correct
28 Correct 5 ms 3792 KB Output is correct
29 Correct 5 ms 3792 KB Output is correct
30 Correct 6 ms 3792 KB Output is correct
31 Correct 5 ms 3664 KB Output is correct
32 Correct 5 ms 3792 KB Output is correct
33 Correct 2 ms 1744 KB Output is correct
34 Correct 5 ms 3800 KB Output is correct
35 Correct 6 ms 3792 KB Output is correct
36 Correct 6 ms 3792 KB Output is correct
37 Correct 5 ms 3792 KB Output is correct
38 Correct 6 ms 3792 KB Output is correct
39 Correct 5 ms 3792 KB Output is correct
40 Correct 5 ms 3792 KB Output is correct
41 Correct 4 ms 3752 KB Output is correct
42 Correct 5 ms 3792 KB Output is correct
43 Correct 4 ms 3792 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 848 KB Output is correct
2 Correct 8 ms 3792 KB Output is correct
3 Correct 7 ms 3792 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 6 ms 3792 KB Output is correct
6 Correct 7 ms 3748 KB Output is correct
7 Correct 6 ms 3792 KB Output is correct
8 Correct 5 ms 3792 KB Output is correct
9 Correct 6 ms 3712 KB Output is correct
10 Correct 5 ms 3792 KB Output is correct
11 Correct 5 ms 3792 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 8 ms 3712 KB Output is correct
14 Correct 5 ms 3664 KB Output is correct
15 Correct 6 ms 3860 KB Output is correct
16 Correct 5 ms 3804 KB Output is correct
17 Correct 6 ms 3792 KB Output is correct
18 Correct 5 ms 3664 KB Output is correct
19 Correct 5 ms 3792 KB Output is correct
20 Correct 5 ms 3784 KB Output is correct
21 Correct 5 ms 3792 KB Output is correct
22 Correct 7 ms 3816 KB Output is correct
23 Correct 6 ms 3704 KB Output is correct
24 Correct 5 ms 3792 KB Output is correct
25 Correct 2 ms 1736 KB Output is correct
26 Correct 9 ms 3760 KB Output is correct
27 Correct 6 ms 3792 KB Output is correct
28 Correct 6 ms 3792 KB Output is correct
29 Correct 5 ms 3792 KB Output is correct
30 Correct 5 ms 3792 KB Output is correct
31 Correct 6 ms 3812 KB Output is correct
32 Correct 6 ms 3792 KB Output is correct
33 Correct 4 ms 3664 KB Output is correct
34 Correct 6 ms 3792 KB Output is correct
35 Correct 7 ms 3792 KB Output is correct
36 Correct 374 ms 159896 KB Output is correct
37 Correct 465 ms 254784 KB Output is correct
38 Correct 449 ms 254976 KB Output is correct
39 Correct 516 ms 254832 KB Output is correct
40 Correct 504 ms 254820 KB Output is correct
41 Correct 503 ms 254848 KB Output is correct
42 Correct 430 ms 254768 KB Output is correct
43 Correct 303 ms 256740 KB Output is correct
44 Correct 315 ms 250568 KB Output is correct
45 Correct 340 ms 254088 KB Output is correct
46 Correct 299 ms 250536 KB Output is correct
47 Correct 476 ms 254868 KB Output is correct
48 Correct 463 ms 254852 KB Output is correct
49 Correct 459 ms 254768 KB Output is correct
50 Correct 391 ms 250528 KB Output is correct
51 Correct 339 ms 256700 KB Output is correct
52 Correct 458 ms 254888 KB Output is correct
53 Correct 554 ms 254880 KB Output is correct
54 Correct 501 ms 254808 KB Output is correct
55 Correct 304 ms 250468 KB Output is correct
56 Correct 331 ms 256916 KB Output is correct
57 Correct 489 ms 245620 KB Output is correct
58 Correct 458 ms 254884 KB Output is correct
59 Correct 464 ms 254892 KB Output is correct
60 Correct 453 ms 254864 KB Output is correct
61 Correct 447 ms 254864 KB Output is correct
62 Correct 461 ms 254924 KB Output is correct
63 Correct 434 ms 254944 KB Output is correct
64 Correct 291 ms 256816 KB Output is correct
65 Correct 295 ms 250648 KB Output is correct
66 Correct 320 ms 256820 KB Output is correct
67 Correct 290 ms 250524 KB Output is correct
68 Correct 1342 ms 252984 KB Output is correct
69 Correct 1504 ms 254852 KB Output is correct
70 Correct 1578 ms 254920 KB Output is correct
71 Correct 1561 ms 254876 KB Output is correct
72 Correct 1487 ms 254964 KB Output is correct
73 Correct 1532 ms 254788 KB Output is correct
74 Correct 1634 ms 254884 KB Output is correct
75 Correct 1422 ms 256804 KB Output is correct
76 Correct 1388 ms 250524 KB Output is correct
77 Correct 1398 ms 254856 KB Output is correct
78 Correct 1410 ms 253676 KB Output is correct
79 Correct 1419 ms 256768 KB Output is correct
80 Correct 1389 ms 250516 KB Output is correct
81 Correct 0 ms 208 KB Output is correct
82 Correct 5 ms 3664 KB Output is correct
83 Correct 5 ms 3664 KB Output is correct
84 Correct 456 ms 254804 KB Output is correct
85 Correct 427 ms 254852 KB Output is correct
86 Correct 429 ms 254896 KB Output is correct
87 Correct 278 ms 250568 KB Output is correct
88 Correct 302 ms 256652 KB Output is correct
89 Correct 437 ms 254768 KB Output is correct
90 Correct 489 ms 254884 KB Output is correct
91 Correct 452 ms 254772 KB Output is correct
92 Correct 307 ms 250604 KB Output is correct
93 Correct 333 ms 256680 KB Output is correct
94 Correct 5 ms 3920 KB Output is correct
95 Correct 5 ms 3792 KB Output is correct
96 Correct 6 ms 3764 KB Output is correct
97 Correct 5 ms 3740 KB Output is correct
98 Correct 6 ms 3792 KB Output is correct
99 Correct 5 ms 3792 KB Output is correct
100 Correct 6 ms 3792 KB Output is correct
101 Correct 5 ms 3792 KB Output is correct
102 Correct 6 ms 3664 KB Output is correct
103 Correct 6 ms 3848 KB Output is correct
104 Correct 1312 ms 224408 KB Output is correct
105 Correct 1608 ms 254916 KB Output is correct
106 Correct 1391 ms 254924 KB Output is correct
107 Correct 1549 ms 254884 KB Output is correct
108 Correct 1625 ms 254896 KB Output is correct
109 Correct 1399 ms 254932 KB Output is correct
110 Correct 1633 ms 255108 KB Output is correct
111 Correct 1101 ms 256828 KB Output is correct
112 Correct 1197 ms 250568 KB Output is correct
113 Correct 1195 ms 256892 KB Output is correct
114 Correct 1363 ms 253872 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 145516 KB Output is correct
2 Correct 1192 ms 256404 KB Output is correct
3 Correct 1304 ms 256444 KB Output is correct
4 Correct 1276 ms 256776 KB Output is correct
5 Correct 1176 ms 250556 KB Output is correct
6 Correct 1452 ms 256672 KB Output is correct
7 Correct 1592 ms 250560 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 7 ms 3664 KB Output is correct
10 Correct 6 ms 3664 KB Output is correct
11 Correct 1 ms 848 KB Output is correct
12 Correct 8 ms 3792 KB Output is correct
13 Correct 7 ms 3792 KB Output is correct
14 Correct 6 ms 3840 KB Output is correct
15 Correct 6 ms 3792 KB Output is correct
16 Correct 7 ms 3748 KB Output is correct
17 Correct 6 ms 3792 KB Output is correct
18 Correct 5 ms 3792 KB Output is correct
19 Correct 6 ms 3712 KB Output is correct
20 Correct 5 ms 3792 KB Output is correct
21 Correct 5 ms 3792 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 8 ms 3712 KB Output is correct
24 Correct 5 ms 3664 KB Output is correct
25 Correct 6 ms 3860 KB Output is correct
26 Correct 5 ms 3804 KB Output is correct
27 Correct 6 ms 3792 KB Output is correct
28 Correct 5 ms 3664 KB Output is correct
29 Correct 5 ms 3792 KB Output is correct
30 Correct 5 ms 3784 KB Output is correct
31 Correct 5 ms 3792 KB Output is correct
32 Correct 7 ms 3816 KB Output is correct
33 Correct 6 ms 3704 KB Output is correct
34 Correct 5 ms 3792 KB Output is correct
35 Correct 2 ms 1736 KB Output is correct
36 Correct 9 ms 3760 KB Output is correct
37 Correct 6 ms 3792 KB Output is correct
38 Correct 6 ms 3792 KB Output is correct
39 Correct 5 ms 3792 KB Output is correct
40 Correct 5 ms 3792 KB Output is correct
41 Correct 6 ms 3812 KB Output is correct
42 Correct 6 ms 3792 KB Output is correct
43 Correct 4 ms 3664 KB Output is correct
44 Correct 6 ms 3792 KB Output is correct
45 Correct 7 ms 3792 KB Output is correct
46 Correct 374 ms 159896 KB Output is correct
47 Correct 465 ms 254784 KB Output is correct
48 Correct 449 ms 254976 KB Output is correct
49 Correct 516 ms 254832 KB Output is correct
50 Correct 504 ms 254820 KB Output is correct
51 Correct 503 ms 254848 KB Output is correct
52 Correct 430 ms 254768 KB Output is correct
53 Correct 303 ms 256740 KB Output is correct
54 Correct 315 ms 250568 KB Output is correct
55 Correct 340 ms 254088 KB Output is correct
56 Correct 299 ms 250536 KB Output is correct
57 Correct 476 ms 254868 KB Output is correct
58 Correct 463 ms 254852 KB Output is correct
59 Correct 459 ms 254768 KB Output is correct
60 Correct 391 ms 250528 KB Output is correct
61 Correct 339 ms 256700 KB Output is correct
62 Correct 458 ms 254888 KB Output is correct
63 Correct 554 ms 254880 KB Output is correct
64 Correct 501 ms 254808 KB Output is correct
65 Correct 304 ms 250468 KB Output is correct
66 Correct 331 ms 256916 KB Output is correct
67 Correct 489 ms 245620 KB Output is correct
68 Correct 458 ms 254884 KB Output is correct
69 Correct 464 ms 254892 KB Output is correct
70 Correct 453 ms 254864 KB Output is correct
71 Correct 447 ms 254864 KB Output is correct
72 Correct 461 ms 254924 KB Output is correct
73 Correct 434 ms 254944 KB Output is correct
74 Correct 291 ms 256816 KB Output is correct
75 Correct 295 ms 250648 KB Output is correct
76 Correct 320 ms 256820 KB Output is correct
77 Correct 290 ms 250524 KB Output is correct
78 Correct 1342 ms 252984 KB Output is correct
79 Correct 1504 ms 254852 KB Output is correct
80 Correct 1578 ms 254920 KB Output is correct
81 Correct 1561 ms 254876 KB Output is correct
82 Correct 1487 ms 254964 KB Output is correct
83 Correct 1532 ms 254788 KB Output is correct
84 Correct 1634 ms 254884 KB Output is correct
85 Correct 1422 ms 256804 KB Output is correct
86 Correct 1388 ms 250524 KB Output is correct
87 Correct 1398 ms 254856 KB Output is correct
88 Correct 1410 ms 253676 KB Output is correct
89 Correct 1419 ms 256768 KB Output is correct
90 Correct 1389 ms 250516 KB Output is correct
91 Correct 0 ms 208 KB Output is correct
92 Correct 5 ms 3664 KB Output is correct
93 Correct 5 ms 3664 KB Output is correct
94 Correct 456 ms 254804 KB Output is correct
95 Correct 427 ms 254852 KB Output is correct
96 Correct 429 ms 254896 KB Output is correct
97 Correct 278 ms 250568 KB Output is correct
98 Correct 302 ms 256652 KB Output is correct
99 Correct 437 ms 254768 KB Output is correct
100 Correct 489 ms 254884 KB Output is correct
101 Correct 452 ms 254772 KB Output is correct
102 Correct 307 ms 250604 KB Output is correct
103 Correct 333 ms 256680 KB Output is correct
104 Correct 5 ms 3920 KB Output is correct
105 Correct 5 ms 3792 KB Output is correct
106 Correct 6 ms 3764 KB Output is correct
107 Correct 5 ms 3740 KB Output is correct
108 Correct 6 ms 3792 KB Output is correct
109 Correct 5 ms 3792 KB Output is correct
110 Correct 6 ms 3792 KB Output is correct
111 Correct 5 ms 3792 KB Output is correct
112 Correct 6 ms 3664 KB Output is correct
113 Correct 6 ms 3848 KB Output is correct
114 Correct 336 ms 54488 KB Output is correct
115 Correct 1397 ms 254992 KB Output is correct
116 Correct 1423 ms 254820 KB Output is correct
117 Correct 1389 ms 254900 KB Output is correct
118 Correct 1402 ms 254904 KB Output is correct
119 Correct 1406 ms 254932 KB Output is correct
120 Correct 1351 ms 254864 KB Output is correct
121 Correct 1293 ms 256828 KB Output is correct
122 Correct 1406 ms 250460 KB Output is correct
123 Correct 1190 ms 256720 KB Output is correct
124 Correct 1128 ms 252096 KB Output is correct
125 Correct 464 ms 254836 KB Output is correct
126 Correct 441 ms 254896 KB Output is correct
127 Correct 446 ms 254900 KB Output is correct
128 Correct 286 ms 250588 KB Output is correct
129 Correct 306 ms 256828 KB Output is correct
130 Correct 424 ms 245720 KB Output is correct
131 Correct 444 ms 254928 KB Output is correct
132 Correct 433 ms 254772 KB Output is correct
133 Correct 453 ms 254872 KB Output is correct
134 Correct 440 ms 254812 KB Output is correct
135 Correct 444 ms 254768 KB Output is correct
136 Correct 459 ms 254932 KB Output is correct
137 Correct 306 ms 256808 KB Output is correct
138 Correct 321 ms 250552 KB Output is correct
139 Correct 303 ms 256856 KB Output is correct
140 Correct 300 ms 250512 KB Output is correct
141 Correct 5 ms 3792 KB Output is correct
142 Correct 5 ms 3792 KB Output is correct
143 Correct 6 ms 3792 KB Output is correct
144 Correct 5 ms 3664 KB Output is correct
145 Correct 5 ms 3792 KB Output is correct
146 Correct 2 ms 1744 KB Output is correct
147 Correct 5 ms 3800 KB Output is correct
148 Correct 6 ms 3792 KB Output is correct
149 Correct 6 ms 3792 KB Output is correct
150 Correct 5 ms 3792 KB Output is correct
151 Correct 6 ms 3792 KB Output is correct
152 Correct 5 ms 3792 KB Output is correct
153 Correct 5 ms 3792 KB Output is correct
154 Correct 4 ms 3752 KB Output is correct
155 Correct 5 ms 3792 KB Output is correct
156 Correct 4 ms 3792 KB Output is correct
157 Correct 1312 ms 224408 KB Output is correct
158 Correct 1608 ms 254916 KB Output is correct
159 Correct 1391 ms 254924 KB Output is correct
160 Correct 1549 ms 254884 KB Output is correct
161 Correct 1625 ms 254896 KB Output is correct
162 Correct 1399 ms 254932 KB Output is correct
163 Correct 1633 ms 255108 KB Output is correct
164 Correct 1101 ms 256828 KB Output is correct
165 Correct 1197 ms 250568 KB Output is correct
166 Correct 1195 ms 256892 KB Output is correct
167 Correct 1363 ms 253872 KB Output is correct
168 Correct 0 ms 208 KB Output is correct
169 Correct 787 ms 81308 KB Output is correct
170 Correct 1691 ms 254888 KB Output is correct
171 Correct 1716 ms 254800 KB Output is correct
172 Correct 1619 ms 254812 KB Output is correct
173 Correct 1728 ms 254928 KB Output is correct
174 Correct 1667 ms 254844 KB Output is correct
175 Correct 1762 ms 254992 KB Output is correct
176 Correct 1259 ms 256780 KB Output is correct
177 Correct 1055 ms 250500 KB Output is correct
178 Correct 1316 ms 253184 KB Output is correct
179 Correct 1384 ms 254156 KB Output is correct