oj.uz

답안 #497606

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
497606 2021-12-23T10:39:12 Z maomao90 새 집 (APIO18_new_home) C++17
100 / 100
 3459 ms 360604 KB 
// When they saw the star, they were overjoyed. On coming to the house,
// they saw the child with his mother Mary, and they bowed down and
// worhipped him. Then they opened their treasures and presented him with 
// gifts of gold, frankincense and myrrh.
// Matthew 2:10-11
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif

#define INF 1500000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 400005

struct store {
	int x, t, a, b;
	bool operator< (const store& o) const {
		return x < o.x;
	}
};
struct qry {
	int l, y, id;
	bool operator< (const qry& o) const {
		return l < o.l;
	}
};
struct ev {
	int t, x, v;
	bool operator< (const ev& o) const {
		return t < o.t;
	}
};
struct ray {
	int x; 
	mutable int h, t;
	bool operator< (const ray& o) const {
		return x < o.x;
	}
	bool operator> (const ray& o) const {
		return x > o.x;
	}
};
struct upd {
	int x, h, s, e;
	bool operator< (const upd& o) const {
		return x < o.x;
	}
};

int n, k, q;
store stores[MAXN];
qry qrys[MAXN];
vector<ev> evs[MAXN];
map<int, int> cnt;
vii dis;
int m;
int ans[MAXN];

vector<upd> zigu, zagu;
void insert(bool b, ray r, int s, int e) {
	if (s > e) return;
	debug("%d %d %d: %d %d\n", b, s, e, r.x, r.h);
	if (!b) {
		zigu.pb((upd) {r.x, r.h, s, e});
	} else {
		zagu.pb((upd) {r.x, r.h, s, e});
	}
}
void dnc(int s, int e, vector<qry> &qrys,
	   	vector<upd> &zigu, vector<upd> &zagu) {
	if (qrys.empty() || zigu.empty()) {
		return;
	}
	debug("%d %d\n", s, e);
	int m = s + e >> 1;
	vector<upd> lzagu, lzigu, rzagu, rzigu, nzagu, nzigu;
	for (upd u : zagu) {
		if (u.s <= s && e <= u.e) {
			debug(" %d %d: %d %d\n", u.s, u.e, u.x, u.h);
			nzagu.pb(u);
			continue;
		}
		if (u.s <= m) {
			lzagu.pb(u);
		}
		if (u.e > m) {
			rzagu.pb(u);
		}
	}
	for (upd u : zigu) {
		if (u.s <= s && e <= u.e) {
			nzigu.pb(u);
			continue;
		}
		if (u.s <= m) {
			lzigu.pb(u);
		}
		if (u.e > m) {
			rzigu.pb(u);
		}
	}
	int ptr = 0;
	for (qry q : qrys) {
		while (ptr < nzagu.size() && nzagu[ptr].x - nzagu[ptr].h < q.l) {
			ptr++;
		}
		if (ptr < nzagu.size()) {
			mxto(ans[q.id], q.l - nzagu[ptr].x);
			debug(" %d: %d\n", q.id, ans[q.id]);
		}
	}
	ptr = 0;
	reverse(ALL(qrys));
	for (qry q : qrys) {
		while (ptr < nzigu.size() && nzigu[ptr].x - nzigu[ptr].h > q.l) {
			ptr++;
		}
		if (ptr < nzigu.size()) {
			mxto(ans[q.id], nzigu[ptr].x - q.l);
			debug(" %d: %d\n", q.id, ans[q.id]);
		}
	}
	reverse(ALL(qrys));
	vector<qry> lqrys, rqrys;
	for (qry q : qrys) {
		if (q.y <= m) {
			lqrys.pb(q);
		} else {
			rqrys.pb(q);
		}
	}
	dnc(s, m, lqrys, lzigu, lzagu);
	dnc(m + 1, e, rqrys, rzigu, rzagu);
}

int main() {
	scanf("%d%d%d", &n, &k, &q);
	REP (i, 0, n) {
		int x, t, a, b; scanf("%d%d%d%d", &x, &t, &a, &b);
		x *= 2;
		stores[i] = (store) {x, t, a, b};
		dis.pb(MP(a, i));
		dis.pb(MP(b, i + n));
	}
	REP (i, 0, q) {
		int l, y; scanf("%d%d", &l, &y);
		l *= 2;
		qrys[i] = (qry) {l, y, i};
		dis.pb(MP(y, i + 2 * n));
	}
	sort(ALL(dis));
	int prv = -1;
	for (auto [a, b] : dis) {
		if (a != prv) {
			m++;
			prv = a;
		}
		if (b < n) {
			stores[b].a = m - 1;
		} else if (b < 2 * n) {
			stores[b - n].b = m - 1;
		} else {
			qrys[b - 2 * n].y = m - 1;
		}
	}
	REP (i, 0, n) {
		debug("%d %d %d %d\n", stores[i].x, stores[i].t, stores[i].a, stores[i].b);
	}
	REP (i, 0, q) {
		debug("%d %d\n", qrys[i].l, qrys[i].y);
	}
	REP (i, 0, n) {
		evs[stores[i].t].pb((ev) {stores[i].a, stores[i].x, 1});
		evs[stores[i].t].pb((ev) {stores[i].b + 1, stores[i].x, -1});
	}
	REP (i, 1, k + 1) {
		evs[i].pb((ev) {0, INF, 1});
		evs[i].pb((ev) {0, -INF, 1});
		sort(ALL(evs[i]));
		{
			set<ray> rays;
			for (ev e : evs[i]) {
				debug(" %d %d %d\n", e.t, e.x, e.v);
				if (e.v == 1) {
					if (e.x != INF && e.x != -INF && cnt[e.x]++ > 0) {
						continue;
					}
					auto it = rays.upper_bound((ray) {e.x, INF, INF});
					if (it != rays.end()) {
						insert(0, *it, it -> t, e.t - 1);
						it -> t = e.t;
						int isect = it -> x - e.x >> 1;
						it -> h = isect;
					}
					if (it == rays.begin()) {
						rays.insert((ray) {e.x, INF, e.t});
					} else {
						it = prev(it);
						assert(it -> x != e.x);
						int isect = e.x - it -> x >> 1;
						rays.insert((ray) {e.x, isect, e.t});
					}
				} else {
					if (--cnt[e.x] > 0) {
						continue;
					}
					auto it = rays.lower_bound((ray) {e.x, -1, -1});
					assert(it -> x == e.x);
					insert(0, *it, it -> t, e.t - 1);
					if (next(it) != rays.end()) {
						auto nxt = next(it);
						insert(0, *nxt, nxt -> t, e.t - 1);
						nxt -> t = e.t;
						nxt -> h += it -> h;
						mnto(nxt -> h, INF);
					}
					rays.erase(it);
				}
			}
			while (!rays.empty()) {
				auto it = rays.begin();
				insert(0, *it, it -> t, m);
				rays.erase(it);
			}
			cnt.clear();
		}
		{
			set<ray, greater<ray>> rays;
			for (ev e : evs[i]) {
				//debug(" %d %d %d\n", e.t, e.x, e.v);
				if (e.v == 1) {
					if (e.x != INF && e.x != -INF && cnt[e.x]++ > 0) {
						continue;
					}
					auto it = rays.upper_bound((ray) {e.x, INF, INF});
					if (it != rays.end()) {
						insert(1, *it, it -> t, e.t - 1);
						it -> t = e.t;
						int isect = it -> x - e.x >> 1;
						it -> h = isect;
					}
					if (it == rays.begin()) {
						rays.insert((ray) {e.x, INF, e.t});
					} else {
						it = prev(it);
						assert(it -> x != e.x);
						int isect = e.x - it -> x >> 1;
						rays.insert((ray) {e.x, isect, e.t});
					}
				} else {
					if (--cnt[e.x] > 0) {
						continue;
					}
					auto it = rays.lower_bound((ray) {e.x, -1, -1});
					assert(it -> x == e.x);
					insert(1, *it, it -> t, e.t - 1);
					if (next(it) != rays.end()) {
						auto nxt = next(it);
						insert(1, *nxt, nxt -> t, e.t - 1);
						nxt -> t = e.t;
						nxt -> h += it -> h;
						mnto(nxt -> h, INF);
					}
					rays.erase(it);
				}
			}
			while (!rays.empty()) {
				auto it = rays.begin();
				insert(1, *it, it -> t, m);
				rays.erase(it);
			}
			cnt.clear();
		}
	}
	sort(ALL(zigu));
	reverse(ALL(zigu));
	sort(ALL(zagu));
	sort(qrys, qrys + q);
	vector<qry> tmp;
	REP (i, 0, q) {
		tmp.pb(qrys[i]);
	}
	dnc(0, m - 1, tmp, zigu, zagu);
	REP (i, 0, q) {
		ans[i] /= 2;
		if (ans[i] > 1e8) {
			ans[i] = -1;
		}
		printf("%d\n", ans[i]);
	}
}

/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

1 1 1
100000000 1 1 1
1 1
*/

Compilation message

new_home.cpp: In function 'void dnc(int, int, std::vector<qry>&, std::vector<upd>&, std::vector<upd>&)':
new_home.cpp:102:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |  int m = s + e >> 1;
      |          ~~^~~
new_home.cpp:131:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   while (ptr < nzagu.size() && nzagu[ptr].x - nzagu[ptr].h < q.l) {
      |          ~~~~^~~~~~~~~~~~~~
new_home.cpp:134:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   if (ptr < nzagu.size()) {
      |       ~~~~^~~~~~~~~~~~~~
new_home.cpp:142:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   while (ptr < nzigu.size() && nzigu[ptr].x - nzigu[ptr].h > q.l) {
      |          ~~~~^~~~~~~~~~~~~~
new_home.cpp:145:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |   if (ptr < nzigu.size()) {
      |       ~~~~^~~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:219:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  219 |       int isect = it -> x - e.x >> 1;
      |                   ~~~~~~~~^~~~~
new_home.cpp:227:23: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  227 |       int isect = e.x - it -> x >> 1;
      |                   ~~~~^~~~~~~~~
new_home.cpp:266:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  266 |       int isect = it -> x - e.x >> 1;
      |                   ~~~~~~~~^~~~~
new_home.cpp:274:23: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  274 |       int isect = e.x - it -> x >> 1;
      |                   ~~~~^~~~~~~~~
new_home.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |  scanf("%d%d%d", &n, &k, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:166:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |   int x, t, a, b; scanf("%d%d%d%d", &x, &t, &a, &b);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:173:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |   int l, y; scanf("%d%d", &l, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9584 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 7 ms 9828 KB Output is correct
6 Correct 8 ms 9932 KB Output is correct
7 Correct 8 ms 10076 KB Output is correct
8 Correct 8 ms 9960 KB Output is correct
9 Correct 8 ms 10084 KB Output is correct
10 Correct 8 ms 9960 KB Output is correct
11 Correct 7 ms 9932 KB Output is correct
12 Correct 8 ms 9964 KB Output is correct
13 Correct 9 ms 9960 KB Output is correct
14 Correct 8 ms 9932 KB Output is correct
15 Correct 8 ms 10060 KB Output is correct
16 Correct 8 ms 10060 KB Output is correct
17 Correct 7 ms 9964 KB Output is correct
18 Correct 7 ms 10024 KB Output is correct
19 Correct 7 ms 10096 KB Output is correct
20 Correct 8 ms 9932 KB Output is correct
21 Correct 7 ms 9840 KB Output is correct
22 Correct 8 ms 10128 KB Output is correct
23 Correct 8 ms 9984 KB Output is correct
24 Correct 8 ms 10072 KB Output is correct
25 Correct 9 ms 9968 KB Output is correct
26 Correct 8 ms 9844 KB Output is correct
27 Correct 7 ms 9932 KB Output is correct
28 Correct 7 ms 9924 KB Output is correct
29 Correct 8 ms 9932 KB Output is correct
30 Correct 6 ms 9840 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9584 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 7 ms 9828 KB Output is correct
6 Correct 8 ms 9932 KB Output is correct
7 Correct 8 ms 10076 KB Output is correct
8 Correct 8 ms 9960 KB Output is correct
9 Correct 8 ms 10084 KB Output is correct
10 Correct 8 ms 9960 KB Output is correct
11 Correct 7 ms 9932 KB Output is correct
12 Correct 8 ms 9964 KB Output is correct
13 Correct 9 ms 9960 KB Output is correct
14 Correct 8 ms 9932 KB Output is correct
15 Correct 8 ms 10060 KB Output is correct
16 Correct 8 ms 10060 KB Output is correct
17 Correct 7 ms 9964 KB Output is correct
18 Correct 7 ms 10024 KB Output is correct
19 Correct 7 ms 10096 KB Output is correct
20 Correct 8 ms 9932 KB Output is correct
21 Correct 7 ms 9840 KB Output is correct
22 Correct 8 ms 10128 KB Output is correct
23 Correct 8 ms 9984 KB Output is correct
24 Correct 8 ms 10072 KB Output is correct
25 Correct 9 ms 9968 KB Output is correct
26 Correct 8 ms 9844 KB Output is correct
27 Correct 7 ms 9932 KB Output is correct
28 Correct 7 ms 9924 KB Output is correct
29 Correct 8 ms 9932 KB Output is correct
30 Correct 6 ms 9840 KB Output is correct
31 Correct 488 ms 50844 KB Output is correct
32 Correct 70 ms 17968 KB Output is correct
33 Correct 520 ms 45584 KB Output is correct
34 Correct 520 ms 46676 KB Output is correct
35 Correct 499 ms 49264 KB Output is correct
36 Correct 496 ms 49196 KB Output is correct
37 Correct 442 ms 41324 KB Output is correct
38 Correct 456 ms 39836 KB Output is correct
39 Correct 394 ms 37576 KB Output is correct
40 Correct 418 ms 38124 KB Output is correct
41 Correct 401 ms 40364 KB Output is correct
42 Correct 401 ms 40396 KB Output is correct
43 Correct 58 ms 21552 KB Output is correct
44 Correct 395 ms 40160 KB Output is correct
45 Correct 379 ms 38600 KB Output is correct
46 Correct 344 ms 39188 KB Output is correct
47 Correct 295 ms 37320 KB Output is correct
48 Correct 284 ms 36556 KB Output is correct
49 Correct 326 ms 38268 KB Output is correct
50 Correct 371 ms 39964 KB Output is correct
51 Correct 321 ms 37920 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 571 ms 117080 KB Output is correct
2 Correct 941 ms 74972 KB Output is correct
3 Correct 788 ms 315760 KB Output is correct
4 Correct 615 ms 156228 KB Output is correct
5 Correct 2182 ms 100056 KB Output is correct
6 Correct 1197 ms 76628 KB Output is correct
7 Correct 862 ms 318264 KB Output is correct
8 Correct 663 ms 157832 KB Output is correct
9 Correct 596 ms 98508 KB Output is correct
10 Correct 748 ms 73124 KB Output is correct
11 Correct 709 ms 76932 KB Output is correct
12 Correct 652 ms 73092 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1884 ms 153252 KB Output is correct
2 Correct 331 ms 49416 KB Output is correct
3 Correct 2193 ms 166724 KB Output is correct
4 Correct 1822 ms 265816 KB Output is correct
5 Correct 1812 ms 189456 KB Output is correct
6 Correct 1796 ms 206092 KB Output is correct
7 Correct 3459 ms 158832 KB Output is correct
8 Correct 2343 ms 160216 KB Output is correct
9 Correct 1542 ms 277728 KB Output is correct
10 Correct 1676 ms 196788 KB Output is correct
11 Correct 1664 ms 179252 KB Output is correct
12 Correct 1930 ms 163876 KB Output is correct
13 Correct 1525 ms 135660 KB Output is correct
14 Correct 1546 ms 144788 KB Output is correct
15 Correct 1603 ms 139948 KB Output is correct
16 Correct 1580 ms 141156 KB Output is correct
17 Correct 1761 ms 137484 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9584 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 7 ms 9828 KB Output is correct
6 Correct 8 ms 9932 KB Output is correct
7 Correct 8 ms 10076 KB Output is correct
8 Correct 8 ms 9960 KB Output is correct
9 Correct 8 ms 10084 KB Output is correct
10 Correct 8 ms 9960 KB Output is correct
11 Correct 7 ms 9932 KB Output is correct
12 Correct 8 ms 9964 KB Output is correct
13 Correct 9 ms 9960 KB Output is correct
14 Correct 8 ms 9932 KB Output is correct
15 Correct 8 ms 10060 KB Output is correct
16 Correct 8 ms 10060 KB Output is correct
17 Correct 7 ms 9964 KB Output is correct
18 Correct 7 ms 10024 KB Output is correct
19 Correct 7 ms 10096 KB Output is correct
20 Correct 8 ms 9932 KB Output is correct
21 Correct 7 ms 9840 KB Output is correct
22 Correct 8 ms 10128 KB Output is correct
23 Correct 8 ms 9984 KB Output is correct
24 Correct 8 ms 10072 KB Output is correct
25 Correct 9 ms 9968 KB Output is correct
26 Correct 8 ms 9844 KB Output is correct
27 Correct 7 ms 9932 KB Output is correct
28 Correct 7 ms 9924 KB Output is correct
29 Correct 8 ms 9932 KB Output is correct
30 Correct 6 ms 9840 KB Output is correct
31 Correct 488 ms 50844 KB Output is correct
32 Correct 70 ms 17968 KB Output is correct
33 Correct 520 ms 45584 KB Output is correct
34 Correct 520 ms 46676 KB Output is correct
35 Correct 499 ms 49264 KB Output is correct
36 Correct 496 ms 49196 KB Output is correct
37 Correct 442 ms 41324 KB Output is correct
38 Correct 456 ms 39836 KB Output is correct
39 Correct 394 ms 37576 KB Output is correct
40 Correct 418 ms 38124 KB Output is correct
41 Correct 401 ms 40364 KB Output is correct
42 Correct 401 ms 40396 KB Output is correct
43 Correct 58 ms 21552 KB Output is correct
44 Correct 395 ms 40160 KB Output is correct
45 Correct 379 ms 38600 KB Output is correct
46 Correct 344 ms 39188 KB Output is correct
47 Correct 295 ms 37320 KB Output is correct
48 Correct 284 ms 36556 KB Output is correct
49 Correct 326 ms 38268 KB Output is correct
50 Correct 371 ms 39964 KB Output is correct
51 Correct 321 ms 37920 KB Output is correct
52 Correct 473 ms 73372 KB Output is correct
53 Correct 483 ms 70588 KB Output is correct
54 Correct 480 ms 57952 KB Output is correct
55 Correct 399 ms 55956 KB Output is correct
56 Correct 380 ms 62676 KB Output is correct
57 Correct 417 ms 47536 KB Output is correct
58 Correct 430 ms 55648 KB Output is correct
59 Correct 447 ms 61184 KB Output is correct
60 Correct 416 ms 44612 KB Output is correct
61 Correct 110 ms 40104 KB Output is correct
62 Correct 450 ms 78308 KB Output is correct
63 Correct 464 ms 64996 KB Output is correct
64 Correct 470 ms 60708 KB Output is correct
65 Correct 452 ms 49964 KB Output is correct
66 Correct 420 ms 39292 KB Output is correct
67 Correct 159 ms 42504 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9584 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 7 ms 9828 KB Output is correct
6 Correct 8 ms 9932 KB Output is correct
7 Correct 8 ms 10076 KB Output is correct
8 Correct 8 ms 9960 KB Output is correct
9 Correct 8 ms 10084 KB Output is correct
10 Correct 8 ms 9960 KB Output is correct
11 Correct 7 ms 9932 KB Output is correct
12 Correct 8 ms 9964 KB Output is correct
13 Correct 9 ms 9960 KB Output is correct
14 Correct 8 ms 9932 KB Output is correct
15 Correct 8 ms 10060 KB Output is correct
16 Correct 8 ms 10060 KB Output is correct
17 Correct 7 ms 9964 KB Output is correct
18 Correct 7 ms 10024 KB Output is correct
19 Correct 7 ms 10096 KB Output is correct
20 Correct 8 ms 9932 KB Output is correct
21 Correct 7 ms 9840 KB Output is correct
22 Correct 8 ms 10128 KB Output is correct
23 Correct 8 ms 9984 KB Output is correct
24 Correct 8 ms 10072 KB Output is correct
25 Correct 9 ms 9968 KB Output is correct
26 Correct 8 ms 9844 KB Output is correct
27 Correct 7 ms 9932 KB Output is correct
28 Correct 7 ms 9924 KB Output is correct
29 Correct 8 ms 9932 KB Output is correct
30 Correct 6 ms 9840 KB Output is correct
31 Correct 488 ms 50844 KB Output is correct
32 Correct 70 ms 17968 KB Output is correct
33 Correct 520 ms 45584 KB Output is correct
34 Correct 520 ms 46676 KB Output is correct
35 Correct 499 ms 49264 KB Output is correct
36 Correct 496 ms 49196 KB Output is correct
37 Correct 442 ms 41324 KB Output is correct
38 Correct 456 ms 39836 KB Output is correct
39 Correct 394 ms 37576 KB Output is correct
40 Correct 418 ms 38124 KB Output is correct
41 Correct 401 ms 40364 KB Output is correct
42 Correct 401 ms 40396 KB Output is correct
43 Correct 58 ms 21552 KB Output is correct
44 Correct 395 ms 40160 KB Output is correct
45 Correct 379 ms 38600 KB Output is correct
46 Correct 344 ms 39188 KB Output is correct
47 Correct 295 ms 37320 KB Output is correct
48 Correct 284 ms 36556 KB Output is correct
49 Correct 326 ms 38268 KB Output is correct
50 Correct 371 ms 39964 KB Output is correct
51 Correct 321 ms 37920 KB Output is correct
52 Correct 571 ms 117080 KB Output is correct
53 Correct 941 ms 74972 KB Output is correct
54 Correct 788 ms 315760 KB Output is correct
55 Correct 615 ms 156228 KB Output is correct
56 Correct 2182 ms 100056 KB Output is correct
57 Correct 1197 ms 76628 KB Output is correct
58 Correct 862 ms 318264 KB Output is correct
59 Correct 663 ms 157832 KB Output is correct
60 Correct 596 ms 98508 KB Output is correct
61 Correct 748 ms 73124 KB Output is correct
62 Correct 709 ms 76932 KB Output is correct
63 Correct 652 ms 73092 KB Output is correct
64 Correct 1884 ms 153252 KB Output is correct
65 Correct 331 ms 49416 KB Output is correct
66 Correct 2193 ms 166724 KB Output is correct
67 Correct 1822 ms 265816 KB Output is correct
68 Correct 1812 ms 189456 KB Output is correct
69 Correct 1796 ms 206092 KB Output is correct
70 Correct 3459 ms 158832 KB Output is correct
71 Correct 2343 ms 160216 KB Output is correct
72 Correct 1542 ms 277728 KB Output is correct
73 Correct 1676 ms 196788 KB Output is correct
74 Correct 1664 ms 179252 KB Output is correct
75 Correct 1930 ms 163876 KB Output is correct
76 Correct 1525 ms 135660 KB Output is correct
77 Correct 1546 ms 144788 KB Output is correct
78 Correct 1603 ms 139948 KB Output is correct
79 Correct 1580 ms 141156 KB Output is correct
80 Correct 1761 ms 137484 KB Output is correct
81 Correct 473 ms 73372 KB Output is correct
82 Correct 483 ms 70588 KB Output is correct
83 Correct 480 ms 57952 KB Output is correct
84 Correct 399 ms 55956 KB Output is correct
85 Correct 380 ms 62676 KB Output is correct
86 Correct 417 ms 47536 KB Output is correct
87 Correct 430 ms 55648 KB Output is correct
88 Correct 447 ms 61184 KB Output is correct
89 Correct 416 ms 44612 KB Output is correct
90 Correct 110 ms 40104 KB Output is correct
91 Correct 450 ms 78308 KB Output is correct
92 Correct 464 ms 64996 KB Output is correct
93 Correct 470 ms 60708 KB Output is correct
94 Correct 452 ms 49964 KB Output is correct
95 Correct 420 ms 39292 KB Output is correct
96 Correct 159 ms 42504 KB Output is correct
97 Correct 2689 ms 360604 KB Output is correct
98 Correct 329 ms 50332 KB Output is correct
99 Correct 2930 ms 185888 KB Output is correct
100 Correct 2726 ms 327780 KB Output is correct
101 Correct 2678 ms 258088 KB Output is correct
102 Correct 2982 ms 214208 KB Output is correct
103 Correct 2473 ms 166056 KB Output is correct
104 Correct 2642 ms 163080 KB Output is correct
105 Correct 2239 ms 150532 KB Output is correct
106 Correct 2314 ms 152588 KB Output is correct
107 Correct 2122 ms 246104 KB Output is correct
108 Correct 2037 ms 308736 KB Output is correct
109 Correct 2232 ms 190516 KB Output is correct
110 Correct 2351 ms 233904 KB Output is correct
111 Correct 2345 ms 259532 KB Output is correct
112 Correct 2278 ms 197980 KB Output is correct
113 Correct 553 ms 169504 KB Output is correct
114 Correct 2487 ms 324160 KB Output is correct
115 Correct 2542 ms 292416 KB Output is correct
116 Correct 2525 ms 270380 KB Output is correct
117 Correct 2407 ms 217564 KB Output is correct
118 Correct 2318 ms 164536 KB Output is correct
119 Correct 768 ms 172760 KB Output is correct
120 Correct 1483 ms 146868 KB Output is correct
121 Correct 1574 ms 148160 KB Output is correct
122 Correct 1513 ms 147368 KB Output is correct
123 Correct 1718 ms 147836 KB Output is correct
124 Correct 1942 ms 154340 KB Output is correct
125 Correct 1722 ms 151016 KB Output is correct
126 Correct 2041 ms 156948 KB Output is correct