oj.uz

Submission #314832

# Submission time Handle Problem Language Result Execution time Memory
314832 2020-10-21T12:36:55 Z Akashi Fish (IOI08_fish) C++14
0 / 100
 497 ms 15224 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 388 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 204 ms 10348 KB Output isn't correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Incorrect 3 ms 416 KB Output isn't correct

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 7032 KB Output is correct
2 Incorrect 265 ms 11384 KB Output isn't correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 245 ms 10360 KB Output isn't correct

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 273 ms 12024 KB Output isn't correct

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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