oj.uz

Submission #548704

# Submission time Handle Problem Language Result Execution time Memory
548704 2022-04-14T10:05:08 Z NachoLibre Fish (IOI08_fish) C++17
100 / 100
 1008 ms 49348 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;

const int F = 500005, K = F;
int f, k, mo, z, c[K];
array<int, 2> a[F], b[F], ab[F];
vector<int> s;
struct oo {
	oo() {
		l = r = 0;
		x = 1;
	}
	oo *l, *r;
	int x;

	void P() {
		int lx = (!l ? 1 : l->x);
		int rx = (!r ? 1 : r->x);
		x = lx * rx % mo;
	}
} *root;

void upd(int i, int x, int l = 1, int r = k, oo *&t = root) {
	if(!t) t = new oo();
	if(l == r) {
		t->x = x % mo;
		return;
	}
	int m = l + r >> 1;
	if(m >= i) upd(i, x, l, m, t->l);
	else upd(i, x, m + 1, r, t->r);
	t->P();
}

void updc(int g) {
	upd(g, c[g] + 1);
}

int x(int sl, int sr, int l = 1, int r = k, oo *&t = root) {
	if(l > sr || r < sl || !t) return 1;
	if(l >= sl && r <= sr) return t->x;
	int m = l + r >> 1;
	return x(sl, sr, l, m, t->l) * x(sl, sr, m + 1, r, t->r) % mo;
}

void moz(int i) {
	while(a[z][0] * 2 > a[i][0]) {
		c[a[z][1]] -= 1;
		updc(a[z][1]);
		z -= 1;
	}
	while(a[z + 1][0] * 2 <= a[i][0]) {
		z += 1;
		c[a[z][1]] += 1;
		updc(a[z][1]);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	#ifdef x
	freopen("x.txt", "r", stdin);
	#endif
	cin >> f >> k >> mo;
	for(int i = 1; i <= f; ++i) {
		cin >> a[i][0] >> a[i][1];
	}
	a[f + 1][0] = 2e9;
	a[f + 1][1] = k + 1;
	sort(a + 1, a + f + 1);
	vector<int> smxf(f + 2, 0);
	smxf[f + 1] = k + 1;
	{
		vector<int> fg(k + 1, 0);
		int kg = k;
		for(int i = f; i >= 1; --i) {
			if(!fg[a[i][1]]) {
				fg[a[i][1]] = kg;
				kg -= 1;
			}
		}
		assert(kg == 0);
		for(int i = 1; i <= f; ++i) {
			a[i][1] = fg[a[i][1]];
			b[i][0] = a[i][1];
			b[i][1] = i;
		}
		sort(b + 1, b + f + 1);
		for(int i = 1; i <= k; ++i) {
			ab[i][0] = 1e9;
		}
		for(int i = 1; i <= f; ++i) {
			ab[b[i][0]][0] = min(ab[b[i][0]][0], i - 1);
			ab[b[i][0]][1] = i;
			s.push_back(b[i][1]);
		}
		vector<bool> fasd(f + 1, 0);
		for(int i = f; i >= 1; --i) {
			smxf[i] = smxf[i + 1];
			if(!fasd[a[i][1]]) {
				fasd[a[i][1]] = 1;
				smxf[i] = a[i][1];
			}
		}
	}
	moz(f);
	int fp = x(1, k);
	vector<bool> xm(k + 1);
	xm[k] = 1;
	for(int i = f - 1; i >= 1; --i) {
		if(!xm[a[i][1]]) {
			xm[a[i][1]] = 1;
			moz(i);
			upd(a[i][1], c[a[i][1]]);
			(fp += x(1, a[i][1])) %= mo;
			updc(a[i][1]);
			int y = *upper_bound(s.begin() + ab[a[i][1]][0], s.begin() + ab[a[i][1]][1], z);
			int l = y + 1, r = f + 1;
			while(l < r) {
				int m = l + r >> 1;
				if(a[y][0] * 2 <= a[m][0]) r = m;
				else l = m + 1;
			}
			int ff = smxf[l];
			fp += x(1, a[i][1] - 1) * x(a[i][1] + 1, ff - 1) % mo;
			fp %= mo;
		}
	}
	assert(fp >= 0 && fp < mo);
	cout << fp << endl;
	return 0;
}

Compilation message

fish.cpp: In function 'void upd(int, int, int, int, oo*&)':
fish.cpp:33:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |  int m = l + r >> 1;
      |          ~~^~~
fish.cpp: In function 'int x(int, int, int, int, oo*&)':
fish.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int m = l + r >> 1;
      |          ~~^~~
fish.cpp: In function 'int main()':
fish.cpp:125:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |     int m = l + r >> 1;
      |             ~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 259 ms 12288 KB Output is correct

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 5416 KB Output is correct
2 Correct 139 ms 6384 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 8384 KB Output is correct
2 Correct 292 ms 12300 KB Output is correct
3 Correct 302 ms 19000 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 12244 KB Output is correct
2 Correct 272 ms 12308 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 8388 KB Output is correct
2 Correct 279 ms 12604 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 11800 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 13424 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 13464 KB Output is correct
2 Correct 335 ms 19080 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 22120 KB Output is correct
2 Correct 455 ms 18560 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 22104 KB Output is correct
2 Correct 613 ms 19452 KB Output is correct
3 Correct 600 ms 26884 KB Output is correct
4 Correct 579 ms 19756 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 875 ms 27068 KB Output is correct
2 Correct 1008 ms 49348 KB Output is correct
3 Correct 719 ms 47368 KB Output is correct
4 Correct 984 ms 41884 KB Output is correct