제출 #297223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
297223		Kastanda	Fish (IOI08_fish)	C++11	9 / 100	548 ms	16888 KiB

fish

// M
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 500005;
int n, k, Mod, C[N], M[N], Last[N], S[N * 2], MX[N];
pair < int , int > A[N];
inline void Set(int i, int val)
{
	S[i += k - 1] = val;
	for (; i; i >>= 1)
		S[i >> 1] = S[i] * 1LL * S[i ^ 1] % Mod;
}
inline int GetMult(int l, int r)
{
	int rt = 1;
	for (l += k - 1, r += k - 1; l < r; l >>= 1, r >>= 1)
	{
		if (l & 1) rt = rt * 1LL * S[l ++] % Mod;
		if (r & 1) rt = rt * 1LL * S[-- r] % Mod;
	}
	return rt;
}
int main()
{
	scanf("%d%d%d", &n, &k, &Mod);
	for (int i = 1; i <= n; i ++)
		scanf("%d%d", &A[i].x, &A[i].y);
	sort(A + 1, A + n + 1);
	for (int i = 1; i <= n; i ++)
		Last[A[i].y] = i;
	int r = 1;
	while (r < n && A[r].x * 2 <= A[n].x)
		r ++;
	int l = 1;
	int tot = 0;
	for (int i = 1; i <= k; i ++)
		Set(i, 1);
	for (int i = 1; i <= n; i ++)
		if (A[i].x * 2 <= A[n].x)
			MX[A[i].y] ++;
	for (int i = r; i <= n; i ++)
		if (Last[A[i].y] == i)
		{
			while (l <= n && A[l].x * 2 <= A[i].x)
			{
				C[A[l].y] ++;
				Set(A[l].y, C[A[l].y] + 1);
				l ++;
			}
			if (MX[A[i].y] >= C[A[i].y] + 1)
				continue;
			int vl = GetMult(1, A[i].y) * 1LL * GetMult(A[i].y + 1, k + 1) % Mod;
			if (i == n)
				vl = vl * 1LL * (C[A[i].y] + 1) % Mod;
			tot = (tot + vl) % Mod;
		}
	M[A[n].y] = 1;
	for (int i = 1; i <= k; i ++)
		Set(i, 1), C[i] = 0;
	l = 1;
	while (l < n)
	{
		if (!M[A[l].y])
		{
			C[A[l].y] ++;
			Set(A[l].y, C[A[l].y] + 1);
		}
		l ++;
	}
	for (int i = n - 1; i; i --)
		if (!M[A[i].y])
		{
			while (l > 1 && A[l - 1].x * 2 > A[i].x)
			{
				l --;
				if (!M[A[l].y])
				{
					C[A[l].y] --;
					Set(A[l].y, C[A[l].y] + 1);
				}
			}
			int vl = GetMult(1, A[i].y) * 1LL * GetMult(A[i].y + 1, k + 1) % Mod;
			if (A[i].x * 2 > A[n].x && MX[A[i].y] < C[A[i].y] + 1)
				vl = vl * 1LL * (C[A[i].y]) % Mod;
			else
				vl = vl * 1LL * (C[A[i].y] + 1) % Mod;
			tot = (tot + vl) % Mod;
			C[A[i].y] = 0;
			M[A[i].y] = 1;
			Set(A[i].y, 1);
		}
	return !printf("%d\n", tot);
}

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'int main()':
fish.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |  scanf("%d%d%d", &n, &k, &Mod);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |   scanf("%d%d", &A[i].x, &A[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 5 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5