Submission #298178

#	Time	Username	Problem	Language	Result	Execution time	Memory
298178		Kastanda	Fish (IOI08_fish)	C++11	100 / 100	1133 ms	48632 KiB

fish

// M
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 500005;
int n, k, Mod, P[N], Rev[N], C[N], S[N * 2];
pair < int , int > A[N];
vector < int > V[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 ++)
		V[A[i].y].push_back(i);
	for (int i = 1; i <= k; i ++)
		P[i] = i;
	sort(P + 1, P + k + 1, [&](int i, int j){return V[i].back() < V[j].back();});
	for (int i = 1; i <= k; i ++)
		Rev[P[i]] = i;
	for (int i = 1; i <= k; i ++)
		Set(i, 1);
	int l = 1, tot = 0;
	for (int i = 1; i <= n; i ++)
		if (V[A[i].y].back() == i)
		{
			while (A[l].x * 2 <= A[i].x)
				C[A[l].y] ++, Set(Rev[A[l].y], C[A[l].y] + 1), l ++;
			int p = 0;
			while (A[V[A[i].y][p]].x * 2 <= A[i].x)
				p ++;
			int le = 1, ri = n + 1, md;
			while (ri - le > 1)
			{
				md = (le + ri) >> 1;
				if (A[md].x >= A[V[A[i].y][p]].x * 2)
					ri = md;
				else
					le = md;
			}
			V[0] = {ri};
			int lb = lower_bound(P + 1, P + k + 1, 0, [&](int a, int b){return V[a].back() < V[b].back();}) - P;
			Set(Rev[A[i].y], 1);
			tot = (tot + GetMult(1, lb)) % Mod;
			Set(Rev[A[i].y], C[A[i].y]);
			tot = (tot + GetMult(1, Rev[A[i].y] + 1)) % Mod;
			Set(Rev[A[i].y], C[A[i].y] + 1);
		}
	return !printf("%d\n", tot);
}

Compilation message (stderr)

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

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