oj.uz

Submission #678312

# Submission time Handle Problem Language Result Execution time Memory
678312 2023-01-05T12:36:20 Z vjudge1 Fish (IOI08_fish) C++17
0 / 100
 473 ms 65536 KB 
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 1e6+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 22;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, k, m;
pair<int, int> niz[maxn];
int cnt[maxn];
int tour[treesiz];
bool bio[maxn];
int id[maxn], fir[maxn];
int nex[maxn], las[maxn];
vector< int > v[maxn];

int mul(int a, int b) {
	a %= m, b %= m;
	return (a * b) % m;
}

void update(int x, int val) {
	x += off;
	tour[x] += val;

	x /= 2;
	while (x > 0) tour[x] = mul(tour[x * 2], tour[x * 2 + 1]), x /= 2;
}

int query(int a, int b, int l, int r, int node) {
	if (l > b || r < a) return 1;
	if (l >= a && r <= b) return tour[node];

	int mid = (l + r) / 2;
	return mul(query(a, b, l, mid, node * 2), query(a, b, mid + 1, r, node * 2 + 1));
}

int main() {
	scanf("%d%d%d", &n, &k, &m);
	for (int i = 0; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		niz[i] = {a, b};
	}
	sort(niz, niz+n);
	reverse(niz, niz+n);
	int cnt = 1;
	for (int i = 0; i < n; i++) {
		int col = niz[i].Y;
		if (bio[col]) continue;
		bio[col] = true;

		fir[cnt] = i;
		id[col] = cnt++;
	}
	for (int i = 0; i < n; i++) 
		niz[i].Y = id[niz[i].Y];

	for (int i = 0; i < n; i++) 
		v[niz[i].Y].push_back(i);
	for (int i = 1; i <= k; i++) {
		nex[fir[i]] = n;
		for (int tren : v[i]) {
			if (niz[tren].X * 2 <= niz[fir[i]].X) nex[fir[i]] = tren;
		}
	}

	for (int i = 0; i < treesiz; i++) tour[i] = 1;
	for (int i = 0; i < n; i++) update(niz[i].Y, 1);

	int sol = 0;
	int ptr = 0;
	memset(bio, false, sizeof bio);
	for (int i = 0; i < n; i++) {
		int len = niz[i].X;
		int col = niz[i].Y;
		if (bio[col]) continue;
		bio[col] = true;

		while (ptr < n && niz[ptr].X * 2 > niz[i].X) 
			update(niz[ptr++].Y, -1);

		//printf("debug: %d %d (%d) --> %d\n", len, col, i, ptr);
		//for (int i = 1; i <= k; i++) printf("%d ", tour[i + off]); printf("\n");

		update(col, -1);
		sol += query(col, k + 1, 0, off - 1, 1);
		update(col, 1);
		sol %= m;

		int lo = 0, hi = col;
		while (lo < hi) {
			int mid = (lo + hi + 1) / 2;
			if (niz[fir[mid]].X >= 2 * niz[nex[i]].X) lo = mid;
			else hi = mid - 1;
		}
		//printf("found: %d\n", lo);
		sol += mul(query(lo + 1, col - 1, 0, off - 1, 1), query(col + 1, k + 1, 0, off - 1, 1));
		sol %= m;
	}
	printf("%d\n", sol);
	return 0;
}

Compilation message

fish.cpp: In function 'int main()':
fish.cpp:83:7: warning: unused variable 'len' [-Wunused-variable]
   83 |   int len = niz[i].X;
      |       ^~~
fish.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d%d", &n, &k, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fish.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 57532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 57524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 57588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 57548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 57584 KB Output is correct
2 Incorrect 28 ms 57652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 57656 KB Output is correct
2 Incorrect 372 ms 64172 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 57556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 57604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 60616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 57632 KB Output is correct
2 Correct 36 ms 57676 KB Output is correct
3 Incorrect 33 ms 57716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 62012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 459 ms 64924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 63052 KB Output is correct
2 Incorrect 426 ms 64656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 404 ms 64588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 356 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 473 ms 63716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 209 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 168 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 228 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -