結果

問題 No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
コンテスト
ユーザー pengin_2000
提出日時 2026-01-23 23:12:05
言語 C
(gcc 15.2.0)
結果
WA  
実行時間 -
コード長 3,526 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 629 ms
コンパイル使用メモリ 40,712 KB
実行使用メモリ 9,500 KB
最終ジャッジ日時 2026-01-23 23:12:34
合計ジャッジ時間 15,042 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12 WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
long long int T[60004], C[60004], B[60004], D[60004];
long long int h[200005], l, z;
long long int comp_h(long long int a, long long int b)
{
	if (z == 0)
	{
		if (h[a] > h[b])
			return 1;
		else
			return -1;
	}
	else if (z == 1)
	{
		if (D[h[a]] > D[h[b]])
			return 1;
		else if (D[h[a]] < D[h[b]])
			return -1;
		else if (B[h[a]] > B[h[b]])
			return 1;
		else
			return -1;
	}
	else
	{
		if (C[h[a]] > C[h[b]])
			return 1;
		else if (C[h[a]] < C[h[b]])
			return -1;
		else if (T[h[a]] > T[h[b]])
			return 1;
		else
			return -1;
	}
}
void swap_h(long long int a, long long int b)
{
	long long int f = h[a];
	h[a] = h[b];
	h[b] = f;
	return;
}
void push(long long int ne)
{
	h[l] = ne;
	long long int p = l++;
	for (; p > 0; p = (p - 1) / 2)
		if (comp_h((p - 1) / 2, p) > 0)
			swap_h((p - 1) / 2, p);
	return;
}
long long int pop()
{
	swap_h(0, --l);
	long long int p = 0;
	for (;;)
	{
		if (2 * p + 2 < l)
		{
			if (comp_h(2 * p + 1, 2 * p + 2) > 0)
			{
				if (comp_h(p, 2 * p + 2) > 0)
					swap_h(p, 2 * p + 2);
				p = 2 * p + 2;
			}
			else
			{
				if (comp_h(p, 2 * p + 1) > 0)
					swap_h(p, 2 * p + 1);
				p = 2 * p + 1;
			}
		}
		else if (2 * p + 1 < l)
		{
			if (comp_h(p, 2 * p + 1) > 0)
				swap_h(p, 2 * p + 1);
			p = 2 * p + 1;
		}
		else
			break;
	}
	return h[l];
}
long long int n, m;
long long int S[200005];
long long int sb1[60004], sb2[60004], id[60004];
long long int I;
long long int cnt[60004];
long long int count(long long int v)
{
	long long int i, min, mid, max, res = 0;
	for (i = 0; i < n; i++)
	{
		cnt[i] = -res;
		min = -1;
		max = m;
		while (max - min > 1)
		{
			mid = (max + min) / 2;
			if (sb1[mid] + T[i] <= v)
				min = mid;
			else
				max = mid;
		}
		res += max;
		min = id[C[i]] - 1;
		max = id[C[i] + 1];
		while (max - min > 1)
		{
			mid = (max + min) / 2;
			if (sb2[mid] + T[i] <= v)
				min = mid;
			else
				max = mid;
		}
		res -= max - id[C[i]];
		min = id[C[i]] - 1;
		max = id[C[i] + 1];
		while (max - min > 1)
		{
			mid = (max + min) / 2;
			if (sb2[mid] + T[i] - S[C[i]] <= v)
				min = mid;
			else
				max = mid;
		}
		res += max - id[C[i]];
		cnt[i] += res;
	}
	return res;
}
long long int cnt1[60004];
void solve()
{
	long long int k, p;
	scanf("%lld %lld %lld %lld", &n, &m, &k, &p);
	long long int i, j;
	for (i = 0; i < n; i++)
		scanf("%lld", &T[i]);
	for (i = 0; i < n; i++)
	{
		scanf("%lld", &C[i]);
		C[i]--;
	}
	for (j = 0; j < m; j++)
		scanf("%lld", &B[j]);
	for (j = 0; j < m; j++)
	{
		scanf("%lld", &D[j]);
		D[j]--;
	}
	for (i = 0; i < k; i++)
		scanf("%lld", &S[i]);
	l = 0;
	z = 0;
	for (j = 0; j < m; j++)
		push(B[j]);
	for (j = 0; j < m; j++)
		sb1[j] = pop();
	z = 1;
	l = 0;
	for (j = 0; j < m; j++)
		push(j);
	for (j = 0; j < m; j++)
		sb2[j] = B[pop()];
	for (j = 0; j <= k; j++)
		id[j] = 0;
	for (j = 0; j < m; j++)
		id[D[j] + 1]++;
	for (j = 0; j < k; j++)
		id[j + 1] += id[j];
	long long int min, mid, max;
	min = -1;
	max = 2e9 + 1;
	while (max - min > 1)
	{
		mid = (max + min) / 2;
		if (count(mid) < p)
			min = mid;
		else
			max = mid;
	}
	long long int v = max, I, J;
	count(v);
	for (i = 0; i < n; i++)
		cnt1[i] = cnt[i];
	count(v - 1);
	for (i = 0; i < n; i++)
		if (cnt[i] < cnt1[i])
			I = i;
	for (j = 0; j < m; j++)
	{
		if (C[I] == D[j])
		{
			if (T[I] + B[j] - S[C[i]] == v)
				J = j;
		}
		else
		{
			if (T[I] + B[j] == v)
				J = j;
		}
	}
	printf("%lld %lld\n", I + 1, J + 1);
	return;
}
int main()
{
	int t;
	scanf("%d", &t);
	for (; t > 0; t--)
		solve();
	return 0;
}
0