oj.uz

Submission #298178

# Submission time Handle Problem Language Result Execution time Memory
298178 2020-09-12T13:55:43 Z Kastanda Fish (IOI08_fish) C++11
100 / 100
 1133 ms 48632 KB 
// 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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12032 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Correct 222 ms 24576 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 17400 KB Output is correct
2 Correct 143 ms 18656 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12288 KB Output is correct
2 Correct 13 ms 12288 KB Output is correct
3 Correct 12 ms 12288 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 20600 KB Output is correct
2 Correct 334 ms 25168 KB Output is correct
3 Correct 262 ms 25576 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 24876 KB Output is correct
2 Correct 258 ms 26236 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 20816 KB Output is correct
2 Correct 279 ms 25832 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 24952 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 27336 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 24752 KB Output is correct
2 Correct 447 ms 30204 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 31024 KB Output is correct
2 Correct 551 ms 27128 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 29944 KB Output is correct
2 Correct 620 ms 30712 KB Output is correct
3 Correct 544 ms 34068 KB Output is correct
4 Correct 610 ms 30584 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 34392 KB Output is correct
2 Correct 727 ms 48632 KB Output is correct
3 Correct 1089 ms 47732 KB Output is correct
4 Correct 1133 ms 44536 KB Output is correct