Submission #1028187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028187		Tob	Fish (IOI08_fish)	C++14	100 / 100	533 ms	65536 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], did[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]) {
			if (fi[c[j]] == j) {
				t2.update(la[c[j]], 1);
				bio[c[j]] = 0;
			}
			cnt[c[j]]--;
			if (bio[c[j]]) {
				if (did[c[j]]) t2.update(la[c[j]], cnt[c[j]]+1);
				else t1.update(fi[c[j]], cnt[c[j]]+1);
			}
			j--;
		}
		if (la[c[i]] == i) {
			t1.update(fi[c[i]], 1);
			ll dod = (ll)t1.query(1, 0, j)*t2.query(1, i, gr[*upper_bound(all(po[c[i]]), ha[i])]);
			if (cnt[c[i]]) {
				t1.update(fi[c[i]], cnt[c[i]]);
				dod += t1.query(1, 0, j);
			}
			res = (res + dod) % mod;
			t1.update(fi[c[i]], 1);
			if (bio[c[i]]) t2.update(i, cnt[c[i]]+1);
			did[c[i]] = 1;
		}
	}
	
	cout << res;

	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 7 / 7
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5