QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#642722#8577. 평균 최대화user1008624 3778ms490216kbC++177.3kb2024-10-15 15:58:312024-10-15 15:58:31

Judging History

你现在查看的是最新测评结果

  • [2024-10-15 15:58:31]
  • 评测
  • 测评结果:24
  • 用时:3778ms
  • 内存:490216kb
  • [2024-10-15 15:58:31]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3e5 + 10;

int n, idx, l[N], r[N], a[N], s[N], rx[N], rs[N];

#define __int128 int

struct F
{
	__int128 i, j;
	
	F()
	{
		i = j = 0;
	}
	
	F(__int128 a, __int128 b)
	{
		__int128 d = __gcd(a, b);
		i = a / d, j = b / d;
	}
	
	bool operator> (const F& f2) const
	{
		return i * f2.j > j * f2.i;
	}
	
	bool operator< (const F& f2) const
	{
		return i * f2.j < j * f2.i;
	}
	
	F operator + (const F& f2) const
	{
		__int128 a = i * f2.j + j * f2.i, b = j * f2.j;
		return {a, b};
	}
	
	void reduce()
	{
		auto d = __gcd(i, j);
		i /= d, j /= d;
	}
	
}ans[N];

	mt19937 rng(20241015);
namespace Tree
{
	
	const int R = 30;
	int idx;
	int ls[N * R], rs[N * R], sz[N * R];
	F tass[N * R];
	F val[N * R], sum[N * R];
	
	void init()
	{
		val[0] = sum[0] = {0, 1};
	}
	
	int newnode(F v)
	{
		idx++;
		assert(idx < N * R);
		ls[idx] = rs[idx] = 0, sz[idx] = 1, tass[idx] = {0, 1};
		val[idx] = sum[idx] = v;
		return idx;
	}
	
	inline void pushup(int u)
	{
		if (!u) return;
		sum[u] = sum[ls[u]] + val[u] + sum[rs[u]];
		sz[u] = sz[ls[u]] + 1 + sz[rs[u]];
	}
	
	inline void apply(int u, const F& dass)
	{
		if (!u) return;
		sum[u] = {dass.i * sz[u], dass.j}, sum[u].reduce(), val[u] = dass;
		tass[u] = dass;
	}
	
	inline void pushdown(int u)
	{
		if (!u) return;
		if (tass[u].i == 0) return;
		apply(ls[u], tass[u]), apply(rs[u], tass[u]);
		tass[u] = {0, 1};
	}
	
	array<int, 2> splitr(int u, int k)
	{
		// [1, k], [k+1, inf)
//		printf("splitr(%lld, %lld)\n", u, k);
		if (!u) return {0, 0};
		pushdown(u);
		if (sz[ls[u]] >= k)
		{
			auto res = splitr(ls[u], k);
			ls[u] = res[1];
			pushup(u);
			return {res[0], u};
		}
		else
		{
			auto res = splitr(rs[u], k - sz[ls[u]] - 1);
			rs[u] = res[0];
			pushup(u);
//			printf("&&&");
			return {u, res[1]};
		}
	}
	
	array<int, 2> splitv(int u, const F& v)
	{
		// [1, v] [v, inf)
		if (!u) return {0, 0};
		pushdown(u);
		if (v > val[u])
		{
			auto res = splitv(ls[u], v);
			ls[u] = res[1];
			pushup(u);
			return {res[0], u};
		}
		else
		{
			auto res = splitv(rs[u], v);
			rs[u] = res[0];
			pushup(u);
			return {u, res[1]};
		}
	}
	
	int merge(int l, int r)
	{
//		printf("merge(%lld, %lld)\n", l, r);
		if (!l) swap(l, r);
		if (!r) return l;
		
		pushdown(l), pushdown(r);
		if (rng() % (sz[l] + sz[r]) < sz[l])
		{
			rs[l] = merge(rs[l], r);
			pushup(l);
			return l;
		}
		else
		{
			ls[r] = merge(l, ls[r]);
			pushup(r);
			return r;
		}
	}
	
	inline void insert(int& rt, const F& v)
	{
		auto res = splitv(rt, v);
		int c = newnode(v);
		rt = merge(merge(res[0], c), res[1]);
	}
	
	inline void assign(int& rt, int pos, const F& v)
	{
		auto res = splitr(rt, pos);
		apply(res[0], v);
		rt = merge(res[0], res[1]);
	}
	
	inline F qsum(int& rt, int pos)
	{
		auto res = splitr(rt, pos);
//		printf("qsum(%lld, %lld)\n", rt, pos);
		F ret = sum[res[0]];
		rt = merge(res[0], res[1]);
		return ret;
	}
	
	void print(int rt)
	{
		if (!rt) return;
		print(ls[rt]), printf("node %lld: sum = %lld/%lld, val = %lld/%lld, tass = %lld/%lld, ls = %lld, rs = %lld\n", rt, sum[rt].i, sum[rt].j, val[rt].i, val[rt].j, tass[rt].i, tass[rt].j, ls[rt], rs[rt]), print(rs[rt]);
	}
}

int dp[N];
vector<int> son[N];
vector<int> rg[N];
map<array<int, 2>, int> mp;

int build(int l, int r)
{
	idx++, ::l[idx] = l, ::r[idx] = r, mp[{l, r}] = idx;
	int x = idx; rx[x] = r - l + 1, rs[x] = s[r] - s[l - 1];
	for (int i = l; i <= r; i++)
	{
		if (rg[i].empty()) continue;
		int j = rg[i].back(); rg[i].pop_back();
		int y = build(i, j);
		son[x].push_back(y);
		rx[x] -= (j - i + 1), rs[x] -= (s[j] - s[i - 1]);
		i = j;
	}
	return x;
}

template<class T>
void chkmax(T &x, T y)
{
	if (y > x) x = y;
}

int merge(int& a, int& b)
{
//	printf("merge(%lld, %lld)\n", a, b);
	if (Tree::sz[a] < Tree::sz[b]) swap(a, b);
	if (!b) return a;
	Tree::pushdown(b);
	merge(a, Tree::ls[b]), Tree::insert(a, Tree::val[b]), merge(a, Tree::rs[b]);
	return a;
}

int pc;

pair<int, F> getp(int& rt, int a, int b)
{
	// max (y - b) / (x - a)
	if (n > 5000) return make_pair(rng() % Tree::sz[rt], F{rng(), rng() % n});
	int l = 0, r = Tree::sz[rt];
	auto getres = [&](int x)
	{
		F y1 = Tree::qsum(rt, x);
		y1.i -= b * y1.j, y1.j *= (x - a);
//		y1.reduce();
		return y1;
	};
	pc++;
	while (l + 1 < r)
	{
		pc++;
//		int mid1 = (l + r) >> 1, mid2 = mid1 + 1;
		int mid1 = l + (r - l + 1) / 3, mid2 = r - (r - l) / 3;
		F y1 = getres(mid1), y2 = getres(mid2);
		if (y1 < y2) l = mid1 + 1;
		else if (y1 > y2) r = mid2 - 1;
		else l = mid1, r = mid2;
	}
//	printf(")))"), Tree::print(rt);
//	printf("res(l) = (%lld, %lld/%lld), res(r) = (%lld, %lld/%lld)\n", l, getres(l).i, getres(l).j, r, getres(r).i, getres(r).j);
	auto resl = getres(l), resr = getres(r);
	resl.reduce(), resr.reduce();
	if (resl > resr) return {l, resl};
	else return {r, resr};
}

void dfs(int x)
{
//	printf("dfs(%lld)\n", x);
	dp[x] = 0;
	if (son[x].empty()) for (int i = 1; i <= rx[x]; i++) Tree::insert(dp[x], {rs[x], rx[x]});
	else 
	{
		for (int y : son[x]) dfs(y), dp[x] = merge(dp[x], dp[y]);
//		Tree::print(dp[x]);
//		 (-rx[x], -rs[x])
		auto res = getp(dp[x], -rx[x], -rs[x]);
//		printf("proc: res = {%lld, %lld/%lld}\n", res.first, res.second.i, res.second.j);
		int p = res.first;
		F v = res.second;
		Tree::assign(dp[x], p, v);
		for (int i = 1; i <= rx[x]; i++) Tree::insert(dp[x], v);
	}
//	Tree::print(dp[x]);
//	cout << "***";
	auto res = getp(dp[x], -2, -(a[l[x] - 1] + a[r[x] + 1]));
	ans[x] = res.second;
//	printf("%lld: (%lld, %lld/%lld)\n", x, res.first, ans[x].i, ans[x].j);
}

void initialize(vector<signed> A)
{
    n = (int)(A.size());
    for (int i = 1; i <= n; i++) a[i] = A[i - 1];
	for (int i = 1; i <= n; i++) s[i] = a[i] + s[i - 1];
    vector<int> s;
    for (int i = n; i >= 1; i--)
    {
    	while (!s.empty() && a[s.back()] > a[i])
    	{
    		int x = s.back(); s.pop_back();
    		if (x != i + 1) rg[i + 1].push_back(x - 1);
    	}
    	if (!s.empty() && s.back() != i + 1) rg[i + 1].push_back(s.back() - 1); 
    	if (!s.empty() && a[s.back()] >= a[i]) s.pop_back();
    	s.push_back(i);
    }
//	for (int i = 1; i <= n; i++)
//		for (int j : rg[i]) printf("[%lld, %lld]\n", i, j);
    
    build(2, n - 1);
//    for (int i = 1; i <= n; i++)
//    	printf("rx[%lld] = %lld, rs[%lld] = %lld\n", i, rx[i], i, rs[i]);
    Tree::init();
    dfs(1);
    
//    for (int i = 1; i <= n; i++)
//    	for (int j = 0; j <= sz[i]; j++)
//    		printf("dp[%lld][%lld] = %lld\n", i, j, dp[i][j]);
    
//    for (int i = 1; i <= n; i++)
//    	for (int j : son[i]) printf("[%lld, %lld] -> [%lld, %lld]\n", l[i], r[i], l[j], r[j]);
}

array<long long, 2> maximum_average(signed i, signed j)
{
	i++, j++;
	if (j == i + 1) return {a[i] + a[j], 2};
	assert(mp.find({i + 1, j - 1}) != mp.end());
	int id = mp[{i + 1, j - 1}];
	return {ans[id].i, ans[id].j};
}

//signed main()
//{
//	int n; cin >> n;
//	vector<signed> A;
//	for (int i = 1, ai; i <= n; i++) cin >> ai, A.push_back(ai); 
//	initialize(A);
//	while (1)
//	{
//		int l, r; cin >> l >> r;
//		auto res = maximum_average(l, r);
//		cout << res[0] << ' ' << res[1] << endl;
//	}
//}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 16ms
memory: 461444kb

input:

10
2 4 3 9 9 9 9 9 9 1
2
0 2
0 9

output:

3 1
20 3

result:

ok correct!

Test #2:

score: 5
Accepted
time: 28ms
memory: 462192kb

input:

15
4596730 8340349 4612555 5692442 3914918 5213545 5248236 1276073 3844119 2943960 9231647 5091649 2239006 9139001 4735414
100
7 8
5 6
2 4
0 4
8 9
10 11
3 4
0 1
10 11
10 11
3 4
4 5
12 13
0 2
2 4
11 12
12 14
2 3
7 8
12 14
6 7
4 5
11 12
10 11
7 12
8 9
8 9
0 2
2 3
12 14
7 9
7 9
12 13
10 11
9 11
13 14
8...

output:

5120192 2
10461781 2
14219915 3
27156994 5
6788079 2
14323296 2
9607360 2
12937079 2
14323296 2
14323296 2
9607360 2
9128463 2
11378007 2
5849878 1
14219915 3
7330655 2
16113421 3
10304997 2
5120192 2
16113421 3
6524309 2
9128463 2
7330655 2
14323296 2
4156467 1
6788079 2
6788079 2
5849878 1
1030499...

result:

ok correct!

Test #3:

score: 5
Accepted
time: 141ms
memory: 461912kb

input:

15
962724 8815662 7612372 5708998 125165 5107756 9366378 9514244 2381600 4299006 9423670 8225791 7458292 2315903 7210561
600000
7 8
0 4
6 8
9 10
11 12
4 5
13 14
8 13
9 11
2 3
7 8
9 12
6 8
0 4
0 2
12 13
1 2
8 13
0 3
9 10
4 5
6 7
6 8
6 7
0 2
4 13
3 4
6 7
8 9
6 7
11 12
5 8
0 3
9 13
4 8
4 8
8 9
8 13
4 1...

output:

11895844 2
23224921 5
21262222 3
13722676 2
15684083 2
5232921 2
9526464 2
17052131 3
21948467 3
13321370 2
11895844 2
29406759 4
21262222 3
23224921 5
17390758 3
9774195 2
16428034 2
17052131 3
5774939 1
13722676 2
5232921 2
18880622 2
21262222 3
18880622 2
17390758 3
11643561 2
5834163 2
18880622 ...

result:

ok correct!

Test #4:

score: 5
Accepted
time: 27ms
memory: 461812kb

input:

15
1 8446287 2 999999 3000000 5533975 3000000 3816891 3000000 7671276 3000000 999999 5836790 8574548 1
23
0 14
1 2
0 1
2 14
0 2
3 11
2 3
4 6
3 4
5 6
4 5
6 8
7 8
6 7
8 10
9 10
8 9
10 11
11 14
12 14
11 12
13 14
12 13

output:

17959923 5
8446289 2
8446288 2
45433481 13
2815430 1
31022140 9
1000001 2
11533975 3
3999999 2
8533975 2
8533975 2
3272297 1
6816891 2
6816891 2
4557092 1
10671276 2
10671276 2
3999999 2
7705669 2
14411339 3
6836789 2
8574549 2
14411338 2

result:

ok correct!

Test #5:

score: 5
Accepted
time: 27ms
memory: 462688kb

input:

15
1 15 16 14 18 13 20 12 22 11 24 10 26 9 1
27
0 14
1 3
0 1
2 3
1 2
3 5
0 3
4 5
3 4
5 7
0 5
6 7
5 6
7 9
0 7
8 9
7 8
9 11
0 9
10 11
9 10
11 13
0 11
12 13
11 12
13 14
0 13

output:

212 15
15 1
16 2
30 2
31 2
15 1
23 2
31 2
32 2
15 1
77 6
32 2
33 2
15 1
109 8
33 2
34 2
15 1
71 5
34 2
35 2
15 1
44 3
35 2
36 2
10 2
211 14

result:

ok correct!

Subtask #2:

score: 6
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 6
Accepted
time: 20ms
memory: 463384kb

input:

48
225555 4046145 5839635 7194994 4703765 1253415 2526352 3198926 6313532 2368195 5024833 9436074 1792945 7650559 3393464 2402026 7697170 5205463 9830460 5392966 1687150 9984223 3014343 8856776 1412298 9773499 6469768 5802450 758943 2748325 7110370 4498454 2674137 8596714 8823659 9855644 6654297 367...

output:

12206599 2
16509941 2
5912798 1
15017401 3
8515643 2
12206599 2
11608824 2
15017401 3
5912798 1
13283417 3
9885780 2
23458015 4
14460907 2
5795490 2
25333600 3
11880653 3
7923098 2
23037954 5
65608557 13
7613747 1
10545933 2
5912798 1
13283417 3
18983962 3
17655565 3
11270851 2
8261027 2
65608557 13...

result:

ok correct!

Test #7:

score: 6
Accepted
time: 136ms
memory: 461396kb

input:

50
7121308 7345583 6899063 282017 6341784 3680369 5436234 9663519 633330 6333746 7783999 6482701 567072 4276742 8011254 1944632 5712778 8002712 306241 4160326 5728910 1328677 6357927 2565549 4232827 255999 3544802 2039097 494486 2383883 9963617 175242 2913048 5502915 9123911 4881811 2516781 8926134 ...

output:

5394962 2
12522742 3
14466891 2
12347500 2
4567430 2
4877210 1
6947205 2
4877210 1
15966363 4
75715129 17
15966363 4
12522742 3
6967076 2
3800801 2
1583596 1
2533583 2
69914912 15
4488826 2
37729565 8
14626826 2
2533583 2
5244361 1
15099753 2
10138859 2
37729565 8
8415963 2
4567430 2
10252153 3
3699...

result:

ok correct!

Test #8:

score: 6
Accepted
time: 20ms
memory: 461764kb

input:

50
1 3859136 7745573 6119170 3863010 2 3 4 3498508 5 6608915 6662164 999999 3000000 7880751 3000000 4473437 3000000 7609368 3000000 4750778 3000000 8554401 3000000 5166495 3000000 4156171 3000000 9941061 3000000 7323881 3000000 3334344 3000000 3959127 3000000 999999 6 5 5322820 9189056 4 8127987 797...

output:

185663885 48
21586891 5
3859137 2
13864743 2
11604709 2
9982180 2
17723879 3
3863012 2
21586889 4
82038497 21
10793446 3
145705920 37
5 2
11781677 3
7 2
3498513 2
3498512 2
3968837 1
3498517 3
4757026 1
6608920 2
7662163 2
13271079 2
46850085 11
14271083 4
4626917 1
3999999 2
10880751 2
10880751 2
1...

result:

ok correct!

Test #9:

score: 6
Accepted
time: 16ms
memory: 461768kb

input:

50
1 50 51 49 53 48 55 47 57 46 59 45 61 44 63 43 65 42 67 41 69 40 71 39 73 38 75 37 77 36 79 35 81 34 83 33 85 32 87 31 89 30 91 29 93 28 95 27 97 1
97
0 49
1 3
0 1
2 3
1 2
3 5
0 3
4 5
3 4
5 7
0 5
6 7
5 6
7 9
0 7
8 9
7 8
9 11
0 9
10 11
9 10
11 13
0 11
12 13
11 12
13 15
0 13
14 15
13 14
15 17
0 15
...

output:

1757 32
50 1
51 2
100 2
101 2
50 1
151 4
101 2
102 2
50 1
42 1
102 2
103 2
50 1
177 4
103 2
104 2
50 1
457 10
104 2
105 2
50 1
187 4
105 2
106 2
50 1
333 7
106 2
107 2
50 1
193 4
107 2
108 2
50 1
293 6
108 2
109 2
50 1
987 20
109 2
110 2
50 1
548 11
110 2
111 2
50 1
201 4
111 2
112 2
50 1
152 3
112 ...

result:

ok correct!

Subtask #3:

score: 13
Accepted

Dependency #2:

100%
Accepted

Test #10:

score: 13
Accepted
time: 177ms
memory: 461892kb

input:

240
6858784 4989917 9746109 9800650 9356541 6503323 7401498 4493451 2801567 3386165 2481047 9837911 8949606 8663384 5535990 833163 922389 2217653 4643612 8798924 859732 616449 7786902 4457600 9298353 6097782 1517199 1575123 3272602 8273488 8507227 5716403 4182244 3701458 1150320 7526997 7126600 8466...

output:

16368254 2
7471044 2
3795476 1
3195008 2
9658656 2
15523880 2
3140042 2
6387963 1
9688346 3
3267230 2
10959355 2
11038795 2
9761526 2
7883702 2
14605972 2
15088697 2
17640709 2
4918214 2
12100367 2
14887508 5
6296185 2
876017 2
6164558 2
4435943 1
19546759 2
8377911 2
14987510 3
20631197 3
18398272 ...

result:

ok correct!

Test #11:

score: 13
Accepted
time: 155ms
memory: 461432kb

input:

250
9162966 9250357 6273148 7600740 9150271 3440942 4849415 2773878 7306022 1849591 6777991 6901659 4064680 3770893 2377669 3403916 1041109 5311874 292665 7289044 3159603 8135675 2072980 3799891 6274489 6899891 9079095 2442557 7502677 3860726 6264634 6932504 7576167 5899943 684774 526401 3720387 478...

output:

13245794 2
11742785 2
6031433 2
10675715 2
6162102 2
6730651 1
6228058 2
9328707 2
5352729 1
19593921 4
15150407 2
9772981 2
13298615 3
11521652 2
6419440 1
12591217 2
11742785 2
39810154 7
34160076 7
3424227 1
10818508 2
8130335 2
16893087 2
16166441 3
15978986 2
7211306 1
10682015 2
3122301 2
6814...

result:

ok correct!

Test #12:

score: 13
Accepted
time: 28ms
memory: 461308kb

input:

250
1 2 3 4 3023964 5 6 9869160 7 8 9359655 9 10 11 5236313 12 6350687 9627762 13 8024104 6527059 3760432 14 15 8480107 16 5445579 7101107 17 18 19 20 7945165 8246903 21 22 23 5152223 24 25 5367561 5181329 9262413 8141382 9514495 26 27 7821178 28 7804811 4208465 6461584 3421272 6286889 4843702 31961...

output:

218222325 47
193204775 42
3 2
183143121 38
5 2
109375705 21
7 2
3023969 2
3023968 2
109375697 19
1007991 1
898221189 203
11 2
9869167 2
9869166 2
30868282 7
9869173 3
824453783 188
15 2
9359664 2
9359663 2
267350406 61
9359672 3
802051200 181
19 2
262713853 59
21 2
5236325 2
5236324 2
27058793 6
523...

result:

ok correct!

Test #13:

score: 13
Accepted
time: 36ms
memory: 460680kb

input:

250
1 250 251 249 253 248 255 247 257 246 259 245 261 244 263 243 265 242 267 241 269 240 271 239 273 238 275 237 277 236 279 235 281 234 283 233 285 232 287 231 289 230 291 229 293 228 295 227 297 226 299 225 301 224 303 223 305 222 307 221 309 220 311 219 313 218 315 217 317 216 319 215 321 214 32...

output:

2951 10
250 1
251 2
500 2
501 2
250 1
751 4
501 2
502 2
250 1
626 3
502 2
503 2
250 1
877 4
503 2
504 2
250 1
2257 10
504 2
505 2
250 1
2761 12
505 2
506 2
250 1
1633 7
506 2
507 2
250 1
943 4
507 2
508 2
250 1
4279 18
508 2
509 2
250 1
4787 20
509 2
510 2
250 1
2648 11
510 2
511 2
250 1
2903 12
511...

result:

ok correct!

Test #14:

score: 13
Accepted
time: 36ms
memory: 461604kb

input:

127
1 25 6 44 6 25 5 83 5 25 6 44 6 25 4 162 4 25 6 44 6 25 5 83 5 25 6 44 6 25 3 321 3 25 6 44 6 25 5 83 5 25 6 44 6 25 4 162 4 25 6 44 6 25 5 83 5 25 6 44 6 25 2 640 2 25 6 44 6 25 5 83 5 25 6 44 6 25 4 162 4 25 6 44 6 25 5 83 5 25 6 44 6 25 3 321 3 25 6 44 6 25 5 83 5 25 6 44 6 25 4 162 4 25 6 44...

output:

646 5
31 2
26 2
56 3
32 3
50 2
50 2
12 1
30 2
31 2
31 1
16 1
88 2
88 2
115 7
31 2
30 2
56 3
12 1
50 2
50 2
35 3
29 2
31 2
170 3
62 3
166 2
166 2
104 5
31 2
29 2
56 3
35 3
50 2
50 2
12 1
30 2
31 2
31 1
115 7
88 2
88 2
114 7
31 2
30 2
56 3
12 1
50 2
50 2
34 3
28 2
31 2
109 1
174 5
324 2
324 2
35 1
31 ...

result:

ok correct!

Subtask #4:

score: 0
Wrong Answer

Test #15:

score: 0
Wrong Answer
time: 3778ms
memory: 490216kb

input:

300000
1 2 4 4 4 4 3 2 4 4 3 4 4 4 4 4 4 4 4 4 3 4 3 4 4 4 4 4 4 4 4 3 3 4 4 4 3 4 3 4 4 4 4 4 4 4 4 4 4 3 3 4 4 4 3 4 4 3 4 4 4 4 4 4 4 3 2 4 4 4 4 4 4 4 4 4 4 4 4 4 3 4 4 4 4 4 4 4 4 4 4 4 2 4 4 2 4 4 3 4 4 4 2 3 4 4 4 4 4 4 3 2 4 4 4 2 4 4 4 4 4 4 4 4 4 4 4 2 4 4 4 4 4 4 3 4 4 3 4 4 4 4 4 4 4 4 4...

output:

33252877 240105
448655475 54151
3 2
8 2
6 2
8 2
8 2
7 2
5 2
715867758 163129
246495161 211129
8 2
6 2
7 2
88954039 24260
3590480273 13496
8 2
7 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
7 2
3384377367 217538
7 2
7 2
3912453329 245879
8 2
7 2
8 2
8 2
8 2
8 2
8 2
8 2
7 2
6 2
3058356389 5881
8 2
7 2
8 2
7 2
231901...

result:

wrong answer Wrong Answer on query #1: 33252877/240105 != 1041675/278497

Subtask #5:

score: 0
Runtime Error

Dependency #3:

100%
Accepted

Test #16:

score: 12
Accepted
time: 262ms
memory: 463564kb

input:

4000
4344032 9677834 5779172 78801 469320 1789966 1779748 3147679 5049607 6295414 6292231 5874387 8807832 5984181 3228577 3529357 528332 6386101 1795741 5602976 8304581 9750737 24760 627728 7325309 4243675 8356932 6633243 445885 1321623 2252967 181037 8074790 4491070 2320473 8159338 7402667 7485053 ...

output:

11382135 2
19014468 5
2589999 2
14894720 2
20540618 3
6556703 2
10536626 2
18763865 3
4160256 1
5265577 2
33745074 5
6464007 2
18380111 4
5961475 2
3185139 2
15747508 2
28358687 4
3622442 1
16924002 2
36799829 10
15816520 2
10606278 2
23916599 3
38151559 7
3124773 2
11841580 2
7572240 2
6991940 2
45...

result:

ok correct!

Test #17:

score: 12
Accepted
time: 251ms
memory: 463392kb

input:

5000
5790446 4508837 9162136 7149900 6430421 1083368 7398254 672635 6289758 2685219 3248824 7705887 2673096 4210193 980601 8521989 5854838 7771569 4286354 9314430 2298604 7164231 5788878 8584031 101973 3153368 4450775 689282 512512 1525682 5373630 9650756 2076382 8232162 6919671 9574533 1484038 1977...

output:

8509384 2
28428602 5
11860325 2
44963154 11
2043805 1
16158237 2
3478186 1
4721965 2
67286440 11
13896336 2
4643078 1
23806767 5
13519895 2
407215453 71
56564231 10
15190255 4
11860325 2
13307255 2
22668102 5
12072576 2
14598075 2
11828186 2
112029242 19
5989987 2
16310221 3
4932732 2
11374206 2
106...

result:

ok correct!

Test #18:

score: 0
Runtime Error

input:

5000
1 4607944 9209259 5347502 4531540 2 4631148 5114154 5933715 8958872 9999015 7211944 8879151 6894166 3723688 3 3340071 4 8339511 5 5412818 3698545 5920965 6 7 4632316 7761575 6047136 8780729 4902685 8 4052029 4707285 9 9106150 8490532 10 5614384 9995766 8159200 11 3778686 12 13 8637120 14 784611...

output:

Unauthorized output

result:


Subtask #6:

score: 0
Runtime Error

Test #28:

score: 0
Runtime Error

input:

300000
1 300000 300001 299999 300003 299998 300005 299997 300007 299996 300009 299995 300011 299994 300013 299993 300015 299992 300017 299991 300019 299990 300021 299989 300023 299988 300025 299987 300027 299986 300029 299985 300031 299984 300033 299983 300035 299982 300037 299981 300039 299980 3000...

output:

Unauthorized output

result:


Subtask #7:

score: 0
Skipped

Dependency #4:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%