Submission #1027899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027899		Tob	Fish (IOI08_fish)	C++14	0 / 100	369 ms	53752 KiB

fish

#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
• 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