oj.uz

Submission #1027899

# Submission time Handle Problem Language Result Execution time Memory
1027899 2024-07-19T11:12:50 Z Tob Fish (IOI08_fish) C++14
0 / 100
 369 ms 53752 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int F = 5e5 + 7, ofs = (1 << 19);

int f, k, mod;
int h[F], c[F], gr[F], fi[F], la[F], cnt[F], ha[F], bio[F];
vector <int> po[F];

struct T {
	vector <int> t;
	void init() {
		t.clear(); t.resize(2*ofs, 1);
	}
	void update(int x, int val) {
		x += ofs;
		t[x] = val;
		while (x /= 2) t[x] = (ll)t[2*x]*t[2*x+1]%mod;
	}
	int query(int x, int a, int b, int lo = 0, int hi = ofs-1) {
		if (b < lo || hi < a) return 1;
		if (a <= lo && hi <= b) return t[x];
		int mid = (lo + hi) / 2;
		return (ll)query(2*x, a, b, lo, mid)*query(2*x+1, a, b, mid+1, hi)%mod;
	}
} t1, t2;

int main () {
	FIO;
	memset(fi, -1, sizeof fi);
	memset(la, -1, sizeof la);
	memset(ha, -1, sizeof ha);
	cin >> f >> k >> mod;
	
	vector <pii> v;
	for (int i = 0; i < f; i++) {
		cin >> h[i] >> c[i]; c[i]--;
		v.pb({h[i], c[i]});
	}
	sort(all(v));
	for (int i = 0; i < f; i++) h[i] = v[i].F, c[i] = v[i].S;
	t1.init(); t2.init();
	for (int i = f-1, j = f-1; i >= 0; i--) {
		while (2*h[i] <= h[j]) ha[j--] = i;
		gr[i] = j;
		if (la[c[i]] == -1) la[c[i]] = i;
		fi[c[i]] = i;
		cnt[c[i]]++;
	}
	for (int i = 0; i < f; i++) po[c[i]].pb(i);
	for (int i = 0; i < k; i++) {
		bio[i] = 1;
		if (la[i] == -1) continue;
		t1.update(fi[i], cnt[i]+1);
	}
	int res = 0;
	for (int i = f-1, j = f-1; i >= 0; i--) {
		while (j > ha[i]) {
			cnt[c[j]] = max(0, cnt[c[j]]-1);
			t1.update(fi[c[j]], cnt[c[j]]+1);
			if (fi[c[j]] == j) {
				t2.update(j, 1);
				bio[c[j]] = 0;
			}
			j--;
		}
		if (la[c[i]] == i) {
			ll dod = 1;
			if (j != -1) dod = t1.query(1, 0, j);
			dod *= t2.query(1, i, gr[*upper_bound(all(po[c[i]]), ha[i])]);
			res = (res + dod) % mod;
			if (bio[c[i]]) t2.update(i, 2);
			t1.update(fi[c[i]], 1+(cnt[c[i]]=0));
		}
	}
	
	cout << res;

	return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35420 KB Output is correct
2 Incorrect 6 ms 35440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35420 KB Output is correct
2 Incorrect 163 ms 46300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35420 KB Output is correct
2 Correct 10 ms 35640 KB Output is correct
3 Incorrect 11 ms 35676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 42116 KB Output is correct
2 Incorrect 179 ms 53752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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