Submission #314832

#	Time	Username	Problem	Language	Result	Execution time	Memory
314832		Akashi	Fish (IOI08_fish)	C++14	0 / 100	497 ms	15224 KiB

fish

#include <bits/stdc++.h>
using namespace std;

const int DIM = 5e5 + 5;

struct elem {
	int x, y;
	bool operator < (const elem &aux) const {
		if (x != aux.x) return x < aux.x;
		return y < aux.y;
	}
};

int n, k, MOD;
bool used[DIM];
int last[DIM];
int arb[4 * DIM];
elem a[DIM];

void build(int st = 1, int dr = k, int nod = 1) {
	if (st == dr) {
		arb[nod] = 1;
		return ;
	}

	int mij = (st + dr) / 2;
	build(st, mij, nod * 2);
	build(mij + 1, dr, nod * 2 + 1);
	arb[nod] = 1;
}

void update(int pos, int val = 1, int st = 1, int dr = k, int nod = 1) {
	if (st == dr) {
		arb[nod] += val;
		if (arb[nod] >= MOD) arb[nod] -= MOD;
		else if (arb[nod] < 0) arb[nod] += MOD;
		return ;
	}

	int mij = (st + dr) / 2;
	if (pos <= mij) update(pos, val, st, mij, nod * 2);
	else update(pos, val, mij + 1, dr, nod * 2 + 1);

	arb[nod] = 1LL * arb[nod * 2] * arb[nod * 2 + 1] % MOD;
}

void explode(int pos, int st = 1, int dr = k, int nod = 1) {
	if (st == dr) {
		arb[nod] = 1;
		return ;
	}

	int mij = (st + dr) / 2;
	if (pos <= mij) explode(pos, st, mij, nod * 2);
	else explode(pos, mij + 1, dr, nod * 2 + 1);

	arb[nod] = 1LL * arb[nod * 2] * arb[nod * 2 + 1] % MOD;
}

int query(int pos, int st = 1, int dr = k, int nod = 1) {
	if (st == dr) return arb[nod];

	int mij = (st + dr) / 2;
	if (pos <= mij) return 1LL * arb[nod * 2 + 1] * query(pos, st, mij, nod * 2) % MOD;
	return 1LL * arb[nod * 2] * query(pos, mij + 1, dr, nod * 2 + 1) % MOD;
}

int main() {
	scanf("%d%d%d", &n, &k, &MOD);
	//MOD = 1e9 + 7;
	for (int i = 1; i <= n ; ++i)
		scanf("%d%d", &a[i].x, &a[i].y);
	for (int i = 1; i <= k ; ++i) last[i] = 0; 
	
	sort(a + 1, a + n + 1);
	build();

	int j = 1;
	for (int i = 1; i <= n ; ++i) {
		while (a[j].x * 2 <= a[i].x) {
			update(a[j].y);
			++j;
		}
	}

	--j;
  int sol = 0;
	for (int i = n; i >= 1 ; --i) {
		if (used[a[i].y]) continue ;

		while (j > 0 && a[j].x * 2 > a[i].x) {
			if (!used[a[j].y]) update(a[j].y, -1);
			--j;
		}
		
		used[a[i].y] = true;
		sol = sol + arb[1];
		if (sol >= MOD) sol -= MOD;
		explode(a[i].y);
		
	//	cerr << sol << endl;
	}

	printf("%d", sol);

	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 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: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5