oj.uz

Submission #795781

# Submission time Handle Problem Language Result Execution time Memory
795781 2023-07-27T14:49:19 Z marvinthang Real Mountains (CCO23_day1problem2) C++17
25 / 25
 2241 ms 118220 KB 
/*************************************
*    author: marvinthang             *
*    created: 21.07.2023 09:05:59    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

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

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

const int MOD = 1e6 + 3;
namespace Mod {

    inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
        unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
    #ifdef __GNUC__
        asm(
            "divl %4 \n\t"
            : "=a" (d), "=d" (m)
            : "d" (xh), "a" (xl), "r" (y)
        );
    #else
        __asm {
            mov edx, dword ptr[xh];
            mov eax, dword ptr[xl];
            div dword ptr[y];
            mov dword ptr[d], eax;
            mov dword ptr[m], edx;
        };
    #endif
        out_d = d; out_m = m;
    }

    template <class T> T invGeneral(T a, T b) {
        a %= b;
        if (!a) return b == 1 ? 0 : -1;
        T x = invGeneral(b, a);
        return x == -1 ? -1 : ((1 - 1LL * b * x) / a + b) % b;
    }

    template <int MOD>
    struct ModInt {
        
        unsigned int val;

        ModInt(void): val(0) {}
        ModInt(const long long &x) { *this = x; }

        ModInt & normalize(const unsigned int &v) {
            val = v >= MOD ? v - MOD : v;
            return *this;
        }

        bool operator ! (void) { return !val; }

        ModInt & operator = (const ModInt &x) { val = x.val; return *this; }
        ModInt & operator = (const long long &x) { return normalize(x % MOD + MOD); }

        ModInt operator - (void) { return ModInt(MOD - val); }

        ModInt & operator += (const ModInt &other) { return normalize(val + other.val); }
        ModInt & operator -= (const ModInt &other) { return normalize(val + MOD - other.val); }
        ModInt & operator /= (const ModInt &other) { return *this *= other.inv(); }

        ModInt & operator *= (const ModInt &other) {
            unsigned dummy;
            fasterLLDivMod((unsigned long long) val * other.val, MOD, dummy, val);
            return *this;
        }

        ModInt operator + (const ModInt &other) const { return ModInt(*this) += other; }
        ModInt operator - (const ModInt &other) const { return ModInt(*this) -= other; }
        ModInt operator * (const ModInt &other) const { return ModInt(*this) *= other; }
        ModInt operator / (const ModInt &other) const { return ModInt(*this) /= other; }

        ModInt pow(long long n) const {
            assert(n >= 0);
            ModInt res = 1, a = *this;
            for (; n; n >>= 1, a *= a) if (n & 1) res *= a;
            return res;
        }

        ModInt inv(void) const {
            int i = invGeneral((int) val, MOD);
            assert(~i);
            return i;
        }

        ModInt & operator ++ (void) { return *this += 1; }
        ModInt & operator -- (void) { return *this -= 1; }
        ModInt operator ++ (int) { ModInt old = *this; operator ++(); return old; }
        ModInt operator -- (int) { ModInt old = *this; operator --(); return old; }

        friend ModInt operator + (const long long &x, const ModInt &y) { return ModInt(x) + y; }
        friend ModInt operator - (const long long &x, const ModInt &y) { return ModInt(x) - y; }
        friend ModInt operator * (const long long &x, const ModInt &y) { return ModInt(x) * y; }
        friend ModInt operator / (const long long &x, const ModInt &y) { return ModInt(x) / y; }
        friend ostream & operator << (ostream &out, const ModInt &x) { return out << x.val; }
        friend istream & operator >> (istream &in, ModInt &x) { long long a; in >> a; x = a; return in; }

        bool operator < (const ModInt &other) const { return val < other.val; }
        bool operator > (const ModInt &other) const { return val > other.val; }
        bool operator <= (const ModInt &other) const { return val <= other.val; }
        bool operator >= (const ModInt &other) const { return val >= other.val; }
        bool operator == (const ModInt &other) const { return val == other.val; }
        bool operator != (const ModInt &other) const { return val != other.val; }
        explicit operator bool(void) const { return val; }
        explicit operator int(void) const { return val; }

    };  

    using Modular = ModInt <MOD>;

}

using namespace Mod;

// end of template

const int MAX = 1e6 + 6;
const int INF = 1e9 + 7;

int N, H[MAX];

void init(void) {
	cin >> N;
	FORE(i, 1, N) cin >> H[i];
}

vector <int> List[MAX];
int st[MAX << 2];

void build(int i, int l, int r) {
	if (l == r) {
		st[i] = H[l];
		return;
	}
	int m = l + r >> 1;
	build(i << 1, l, m);
	build(i << 1 | 1, m + 1, r);
	st[i] = min(st[i << 1], st[i << 1 | 1]);
}

void update(int i, int l, int r, int p, int v) {
	if (l == r) {
		st[i] = v;
		return;
	}
	int m = l + r >> 1;
	if (p <= m) update(i << 1, l, m, p, v);
	else update(i << 1 | 1, m + 1, r, p, v);
	st[i] = min(st[i << 1], st[i << 1 | 1]);
}

int get(int i, int l, int r, int u, int v) {
	if (l > v || r < u) return INF;
	if (u <= l && r <= v) return st[i];
	int m = l + r >> 1;
	return min(get(i << 1, l, m, u, v), get(i << 1 | 1, m + 1, r, u, v));
}

void process(void) {
	vector <int> values(H + 1, H + 1 + N);
	sort(ALL(values));
	values.erase(unique(ALL(values)), values.end());
	FORE(i, 1, N) {
		H[i] = lower_bound(ALL(values), H[i]) - values.begin();
		List[H[i]].push_back(i);
	}
	build(1, 1, N);
	int l = 1, r = N;
	Modular inv2 = Modular(2).inv(), res;
	set <int> pos(ALL(List[0]));
	for (int u: List[0]) update(1, 1, N, u, INF);
	int mi = 0;
	int last = -1;
	while (l < r) {
		while (!pos.empty() && *pos.begin() <= l) pos.erase(pos.begin());
		while (!pos.empty() && *pos.rbegin() >= r) pos.erase(prev(pos.end()));
		int v = min(H[l], H[r]);
		if (pos.empty()) {
			++mi;
			if (mi == v) ++mi;
			if (mi == max(H[l], H[r])) ++mi;
			pos = set<int>(ALL(List[mi]));
		}
		while (last < mi) {
			++last;
			for (int u: List[last]) update(1, 1, N, u, INF);
		}
		if (mi < v) {
			int tl = *pos.begin(), tr = *pos.rbegin(), cnt = pos.size();
			int hl = get(1, 1, N, 1, tl - 1);
			int hm = get(1, 1, N, tl + 1, tr - 1);
			int hr = get(1, 1, N, tr + 1, N);

			v = min({hl, hm, hr});

			res += inv2 * cnt * (values[v] - values[mi]) * (values[v] + values[mi] - 1);
			if (cnt == 1) res += Modular(values[hl] + values[hr]) * (values[v] - values[mi]);
			else {
				res += Modular((long long) values[hl] + values[hr] + values[v]) * (values[v] - values[mi]);
				res += inv2 * (2 * cnt - 3) * (values[v] - values[mi]) * (values[v] + values[mi] + 1);
			}
			pos.insert(ALL(List[v]));
			mi = v;
		}
		if (v == H[l]) ++l;
		if (v == H[r]) --r;
	}
	cout << res << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("cco23p2");
	init();
	process();
	cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:170:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  170 |  int m = l + r >> 1;
      |          ~~^~~
Main.cpp: In function 'void update(int, int, int, int, int)':
Main.cpp:181:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  181 |  int m = l + r >> 1;
      |          ~~^~~
Main.cpp: In function 'int get(int, int, int, int, int)':
Main.cpp:190:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  190 |  int m = l + r >> 1;
      |          ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:248:2: note: in expansion of macro 'file'
  248 |  file("cco23p2");
      |  ^~~~
Main.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:248:2: note: in expansion of macro 'file'
  248 |  file("cco23p2");
      |  ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 12 ms 24168 KB Output is correct
5 Correct 13 ms 24068 KB Output is correct
6 Correct 12 ms 24176 KB Output is correct
7 Correct 12 ms 24148 KB Output is correct
8 Correct 12 ms 24148 KB Output is correct
9 Correct 12 ms 23884 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 12 ms 24148 KB Output is correct
12 Correct 12 ms 24068 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 12 ms 24168 KB Output is correct
5 Correct 13 ms 24068 KB Output is correct
6 Correct 12 ms 24176 KB Output is correct
7 Correct 12 ms 24148 KB Output is correct
8 Correct 12 ms 24148 KB Output is correct
9 Correct 12 ms 23884 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 12 ms 24148 KB Output is correct
12 Correct 12 ms 24068 KB Output is correct
13 Correct 12 ms 24124 KB Output is correct
14 Correct 10 ms 23708 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 12 ms 24164 KB Output is correct
17 Correct 13 ms 24144 KB Output is correct
18 Correct 13 ms 24108 KB Output is correct
19 Correct 12 ms 24148 KB Output is correct
20 Correct 12 ms 24184 KB Output is correct
21 Correct 12 ms 24148 KB Output is correct
22 Correct 14 ms 24148 KB Output is correct
23 Correct 13 ms 24188 KB Output is correct
24 Correct 12 ms 24148 KB Output is correct
25 Correct 13 ms 24108 KB Output is correct
26 Correct 12 ms 24148 KB Output is correct
27 Correct 12 ms 24148 KB Output is correct
28 Correct 12 ms 24132 KB Output is correct
29 Correct 11 ms 23804 KB Output is correct
30 Correct 11 ms 23764 KB Output is correct
31 Correct 11 ms 23764 KB Output is correct
32 Correct 11 ms 23752 KB Output is correct
33 Correct 11 ms 23808 KB Output is correct
34 Correct 11 ms 23764 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 12 ms 24168 KB Output is correct
5 Correct 13 ms 24068 KB Output is correct
6 Correct 12 ms 24176 KB Output is correct
7 Correct 12 ms 24148 KB Output is correct
8 Correct 12 ms 24148 KB Output is correct
9 Correct 12 ms 23884 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 12 ms 24148 KB Output is correct
12 Correct 12 ms 24068 KB Output is correct
13 Correct 12 ms 24124 KB Output is correct
14 Correct 10 ms 23708 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 12 ms 24164 KB Output is correct
17 Correct 13 ms 24144 KB Output is correct
18 Correct 13 ms 24108 KB Output is correct
19 Correct 12 ms 24148 KB Output is correct
20 Correct 12 ms 24184 KB Output is correct
21 Correct 12 ms 24148 KB Output is correct
22 Correct 14 ms 24148 KB Output is correct
23 Correct 13 ms 24188 KB Output is correct
24 Correct 12 ms 24148 KB Output is correct
25 Correct 13 ms 24108 KB Output is correct
26 Correct 12 ms 24148 KB Output is correct
27 Correct 12 ms 24148 KB Output is correct
28 Correct 12 ms 24132 KB Output is correct
29 Correct 11 ms 23804 KB Output is correct
30 Correct 11 ms 23764 KB Output is correct
31 Correct 11 ms 23764 KB Output is correct
32 Correct 11 ms 23752 KB Output is correct
33 Correct 11 ms 23808 KB Output is correct
34 Correct 11 ms 23764 KB Output is correct
35 Correct 15 ms 24276 KB Output is correct
36 Correct 14 ms 24276 KB Output is correct
37 Correct 15 ms 24276 KB Output is correct
38 Correct 14 ms 24216 KB Output is correct
39 Correct 16 ms 24276 KB Output is correct
40 Correct 13 ms 24076 KB Output is correct
41 Correct 12 ms 24164 KB Output is correct
42 Correct 14 ms 24136 KB Output is correct
43 Correct 15 ms 24276 KB Output is correct
44 Correct 17 ms 24240 KB Output is correct
45 Correct 16 ms 24296 KB Output is correct
46 Correct 15 ms 24276 KB Output is correct
47 Correct 15 ms 24168 KB Output is correct
48 Correct 18 ms 24220 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 12 ms 24168 KB Output is correct
5 Correct 13 ms 24068 KB Output is correct
6 Correct 12 ms 24176 KB Output is correct
7 Correct 12 ms 24148 KB Output is correct
8 Correct 12 ms 24148 KB Output is correct
9 Correct 12 ms 23884 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 12 ms 24148 KB Output is correct
12 Correct 12 ms 24068 KB Output is correct
13 Correct 12 ms 24124 KB Output is correct
14 Correct 10 ms 23708 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 12 ms 24164 KB Output is correct
17 Correct 13 ms 24144 KB Output is correct
18 Correct 13 ms 24108 KB Output is correct
19 Correct 12 ms 24148 KB Output is correct
20 Correct 12 ms 24184 KB Output is correct
21 Correct 12 ms 24148 KB Output is correct
22 Correct 14 ms 24148 KB Output is correct
23 Correct 13 ms 24188 KB Output is correct
24 Correct 12 ms 24148 KB Output is correct
25 Correct 13 ms 24108 KB Output is correct
26 Correct 12 ms 24148 KB Output is correct
27 Correct 12 ms 24148 KB Output is correct
28 Correct 12 ms 24132 KB Output is correct
29 Correct 11 ms 23804 KB Output is correct
30 Correct 11 ms 23764 KB Output is correct
31 Correct 11 ms 23764 KB Output is correct
32 Correct 11 ms 23752 KB Output is correct
33 Correct 11 ms 23808 KB Output is correct
34 Correct 11 ms 23764 KB Output is correct
35 Correct 15 ms 24276 KB Output is correct
36 Correct 14 ms 24276 KB Output is correct
37 Correct 15 ms 24276 KB Output is correct
38 Correct 14 ms 24216 KB Output is correct
39 Correct 16 ms 24276 KB Output is correct
40 Correct 13 ms 24076 KB Output is correct
41 Correct 12 ms 24164 KB Output is correct
42 Correct 14 ms 24136 KB Output is correct
43 Correct 15 ms 24276 KB Output is correct
44 Correct 17 ms 24240 KB Output is correct
45 Correct 16 ms 24296 KB Output is correct
46 Correct 15 ms 24276 KB Output is correct
47 Correct 15 ms 24168 KB Output is correct
48 Correct 18 ms 24220 KB Output is correct
49 Correct 19 ms 24276 KB Output is correct
50 Correct 15 ms 24200 KB Output is correct
51 Correct 15 ms 24276 KB Output is correct
52 Correct 15 ms 24276 KB Output is correct
53 Correct 15 ms 24276 KB Output is correct
54 Correct 16 ms 24148 KB Output is correct
55 Correct 13 ms 24164 KB Output is correct
56 Correct 13 ms 24076 KB Output is correct
57 Correct 15 ms 24236 KB Output is correct
58 Correct 15 ms 24276 KB Output is correct
59 Correct 15 ms 24296 KB Output is correct
60 Correct 15 ms 24276 KB Output is correct
61 Correct 15 ms 24192 KB Output is correct
62 Correct 14 ms 24276 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 12 ms 24168 KB Output is correct
5 Correct 13 ms 24068 KB Output is correct
6 Correct 12 ms 24176 KB Output is correct
7 Correct 12 ms 24148 KB Output is correct
8 Correct 12 ms 24148 KB Output is correct
9 Correct 12 ms 23884 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 12 ms 24148 KB Output is correct
12 Correct 12 ms 24068 KB Output is correct
13 Correct 12 ms 24124 KB Output is correct
14 Correct 10 ms 23708 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 12 ms 24164 KB Output is correct
17 Correct 13 ms 24144 KB Output is correct
18 Correct 13 ms 24108 KB Output is correct
19 Correct 12 ms 24148 KB Output is correct
20 Correct 12 ms 24184 KB Output is correct
21 Correct 12 ms 24148 KB Output is correct
22 Correct 14 ms 24148 KB Output is correct
23 Correct 13 ms 24188 KB Output is correct
24 Correct 12 ms 24148 KB Output is correct
25 Correct 13 ms 24108 KB Output is correct
26 Correct 12 ms 24148 KB Output is correct
27 Correct 12 ms 24148 KB Output is correct
28 Correct 12 ms 24132 KB Output is correct
29 Correct 11 ms 23804 KB Output is correct
30 Correct 11 ms 23764 KB Output is correct
31 Correct 11 ms 23764 KB Output is correct
32 Correct 11 ms 23752 KB Output is correct
33 Correct 11 ms 23808 KB Output is correct
34 Correct 11 ms 23764 KB Output is correct
35 Correct 856 ms 92072 KB Output is correct
36 Correct 841 ms 92052 KB Output is correct
37 Correct 842 ms 92060 KB Output is correct
38 Correct 872 ms 91972 KB Output is correct
39 Correct 851 ms 92088 KB Output is correct
40 Correct 11 ms 23764 KB Output is correct
41 Correct 11 ms 23764 KB Output is correct
42 Correct 425 ms 90780 KB Output is correct
43 Correct 411 ms 90764 KB Output is correct
44 Correct 467 ms 90688 KB Output is correct
45 Correct 332 ms 92060 KB Output is correct
46 Correct 334 ms 92208 KB Output is correct
47 Correct 323 ms 91960 KB Output is correct
48 Correct 445 ms 92108 KB Output is correct
49 Correct 483 ms 92080 KB Output is correct
50 Correct 451 ms 92064 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 12 ms 24168 KB Output is correct
5 Correct 13 ms 24068 KB Output is correct
6 Correct 12 ms 24176 KB Output is correct
7 Correct 12 ms 24148 KB Output is correct
8 Correct 12 ms 24148 KB Output is correct
9 Correct 12 ms 23884 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 12 ms 24148 KB Output is correct
12 Correct 12 ms 24068 KB Output is correct
13 Correct 12 ms 24124 KB Output is correct
14 Correct 10 ms 23708 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 12 ms 24164 KB Output is correct
17 Correct 13 ms 24144 KB Output is correct
18 Correct 13 ms 24108 KB Output is correct
19 Correct 12 ms 24148 KB Output is correct
20 Correct 12 ms 24184 KB Output is correct
21 Correct 12 ms 24148 KB Output is correct
22 Correct 14 ms 24148 KB Output is correct
23 Correct 13 ms 24188 KB Output is correct
24 Correct 12 ms 24148 KB Output is correct
25 Correct 13 ms 24108 KB Output is correct
26 Correct 12 ms 24148 KB Output is correct
27 Correct 12 ms 24148 KB Output is correct
28 Correct 12 ms 24132 KB Output is correct
29 Correct 11 ms 23804 KB Output is correct
30 Correct 11 ms 23764 KB Output is correct
31 Correct 11 ms 23764 KB Output is correct
32 Correct 11 ms 23752 KB Output is correct
33 Correct 11 ms 23808 KB Output is correct
34 Correct 11 ms 23764 KB Output is correct
35 Correct 15 ms 24276 KB Output is correct
36 Correct 14 ms 24276 KB Output is correct
37 Correct 15 ms 24276 KB Output is correct
38 Correct 14 ms 24216 KB Output is correct
39 Correct 16 ms 24276 KB Output is correct
40 Correct 13 ms 24076 KB Output is correct
41 Correct 12 ms 24164 KB Output is correct
42 Correct 14 ms 24136 KB Output is correct
43 Correct 15 ms 24276 KB Output is correct
44 Correct 17 ms 24240 KB Output is correct
45 Correct 16 ms 24296 KB Output is correct
46 Correct 15 ms 24276 KB Output is correct
47 Correct 15 ms 24168 KB Output is correct
48 Correct 18 ms 24220 KB Output is correct
49 Correct 856 ms 92072 KB Output is correct
50 Correct 841 ms 92052 KB Output is correct
51 Correct 842 ms 92060 KB Output is correct
52 Correct 872 ms 91972 KB Output is correct
53 Correct 851 ms 92088 KB Output is correct
54 Correct 11 ms 23764 KB Output is correct
55 Correct 11 ms 23764 KB Output is correct
56 Correct 425 ms 90780 KB Output is correct
57 Correct 411 ms 90764 KB Output is correct
58 Correct 467 ms 90688 KB Output is correct
59 Correct 332 ms 92060 KB Output is correct
60 Correct 334 ms 92208 KB Output is correct
61 Correct 323 ms 91960 KB Output is correct
62 Correct 445 ms 92108 KB Output is correct
63 Correct 483 ms 92080 KB Output is correct
64 Correct 451 ms 92064 KB Output is correct
65 Correct 2005 ms 106540 KB Output is correct
66 Correct 1961 ms 106828 KB Output is correct
67 Correct 1981 ms 106792 KB Output is correct
68 Correct 1986 ms 106668 KB Output is correct
69 Correct 1926 ms 106608 KB Output is correct
70 Correct 413 ms 90712 KB Output is correct
71 Correct 414 ms 90660 KB Output is correct
72 Correct 422 ms 90740 KB Output is correct
73 Correct 820 ms 106556 KB Output is correct
74 Correct 820 ms 106732 KB Output is correct
75 Correct 815 ms 106588 KB Output is correct
76 Correct 1084 ms 106544 KB Output is correct
77 Correct 1096 ms 106360 KB Output is correct
78 Correct 1098 ms 106280 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 12 ms 24168 KB Output is correct
5 Correct 13 ms 24068 KB Output is correct
6 Correct 12 ms 24176 KB Output is correct
7 Correct 12 ms 24148 KB Output is correct
8 Correct 12 ms 24148 KB Output is correct
9 Correct 12 ms 23884 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 12 ms 24148 KB Output is correct
12 Correct 12 ms 24068 KB Output is correct
13 Correct 12 ms 24124 KB Output is correct
14 Correct 10 ms 23708 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 12 ms 24164 KB Output is correct
17 Correct 13 ms 24144 KB Output is correct
18 Correct 13 ms 24108 KB Output is correct
19 Correct 12 ms 24148 KB Output is correct
20 Correct 12 ms 24184 KB Output is correct
21 Correct 12 ms 24148 KB Output is correct
22 Correct 14 ms 24148 KB Output is correct
23 Correct 13 ms 24188 KB Output is correct
24 Correct 12 ms 24148 KB Output is correct
25 Correct 13 ms 24108 KB Output is correct
26 Correct 12 ms 24148 KB Output is correct
27 Correct 12 ms 24148 KB Output is correct
28 Correct 12 ms 24132 KB Output is correct
29 Correct 11 ms 23804 KB Output is correct
30 Correct 11 ms 23764 KB Output is correct
31 Correct 11 ms 23764 KB Output is correct
32 Correct 11 ms 23752 KB Output is correct
33 Correct 11 ms 23808 KB Output is correct
34 Correct 11 ms 23764 KB Output is correct
35 Correct 15 ms 24276 KB Output is correct
36 Correct 14 ms 24276 KB Output is correct
37 Correct 15 ms 24276 KB Output is correct
38 Correct 14 ms 24216 KB Output is correct
39 Correct 16 ms 24276 KB Output is correct
40 Correct 13 ms 24076 KB Output is correct
41 Correct 12 ms 24164 KB Output is correct
42 Correct 14 ms 24136 KB Output is correct
43 Correct 15 ms 24276 KB Output is correct
44 Correct 17 ms 24240 KB Output is correct
45 Correct 16 ms 24296 KB Output is correct
46 Correct 15 ms 24276 KB Output is correct
47 Correct 15 ms 24168 KB Output is correct
48 Correct 18 ms 24220 KB Output is correct
49 Correct 19 ms 24276 KB Output is correct
50 Correct 15 ms 24200 KB Output is correct
51 Correct 15 ms 24276 KB Output is correct
52 Correct 15 ms 24276 KB Output is correct
53 Correct 15 ms 24276 KB Output is correct
54 Correct 16 ms 24148 KB Output is correct
55 Correct 13 ms 24164 KB Output is correct
56 Correct 13 ms 24076 KB Output is correct
57 Correct 15 ms 24236 KB Output is correct
58 Correct 15 ms 24276 KB Output is correct
59 Correct 15 ms 24296 KB Output is correct
60 Correct 15 ms 24276 KB Output is correct
61 Correct 15 ms 24192 KB Output is correct
62 Correct 14 ms 24276 KB Output is correct
63 Correct 856 ms 92072 KB Output is correct
64 Correct 841 ms 92052 KB Output is correct
65 Correct 842 ms 92060 KB Output is correct
66 Correct 872 ms 91972 KB Output is correct
67 Correct 851 ms 92088 KB Output is correct
68 Correct 11 ms 23764 KB Output is correct
69 Correct 11 ms 23764 KB Output is correct
70 Correct 425 ms 90780 KB Output is correct
71 Correct 411 ms 90764 KB Output is correct
72 Correct 467 ms 90688 KB Output is correct
73 Correct 332 ms 92060 KB Output is correct
74 Correct 334 ms 92208 KB Output is correct
75 Correct 323 ms 91960 KB Output is correct
76 Correct 445 ms 92108 KB Output is correct
77 Correct 483 ms 92080 KB Output is correct
78 Correct 451 ms 92064 KB Output is correct
79 Correct 2005 ms 106540 KB Output is correct
80 Correct 1961 ms 106828 KB Output is correct
81 Correct 1981 ms 106792 KB Output is correct
82 Correct 1986 ms 106668 KB Output is correct
83 Correct 1926 ms 106608 KB Output is correct
84 Correct 413 ms 90712 KB Output is correct
85 Correct 414 ms 90660 KB Output is correct
86 Correct 422 ms 90740 KB Output is correct
87 Correct 820 ms 106556 KB Output is correct
88 Correct 820 ms 106732 KB Output is correct
89 Correct 815 ms 106588 KB Output is correct
90 Correct 1084 ms 106544 KB Output is correct
91 Correct 1096 ms 106360 KB Output is correct
92 Correct 1098 ms 106280 KB Output is correct
93 Correct 447 ms 90648 KB Output is correct
94 Correct 1010 ms 118220 KB Output is correct
95 Correct 1008 ms 118108 KB Output is correct
96 Correct 1040 ms 118036 KB Output is correct
97 Correct 1255 ms 117776 KB Output is correct
98 Correct 1366 ms 117780 KB Output is correct
99 Correct 1286 ms 117704 KB Output is correct
100 Correct 2189 ms 118048 KB Output is correct
101 Correct 2233 ms 117980 KB Output is correct
102 Correct 2241 ms 118016 KB Output is correct
103 Correct 2239 ms 117928 KB Output is correct
104 Correct 2229 ms 118144 KB Output is correct
105 Correct 442 ms 90784 KB Output is correct
106 Correct 424 ms 90732 KB Output is correct