Submission #157092

#	Time	Username	Problem	Language	Result	Execution time	Memory
157092		youngyojun	Fish (IOI08_fish)	C++11	90 / 100	985 ms	65536 KiB

fish

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define rb(x) ((x)&(-(x)))
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
const int MAXN = 500005;
const int MAXK = 500005;
const int MX = 1048576;
 
pii QV[MAXK];
vector<int> BV[MAXK], BIV[MAXK];
 
int C[MAXK], O[MAXK], RO[MAXK];
int CI[MAXK], CHI[MAXK], BI[MAXN];
int A[MAXN], B[MAXN];
 
ll Ans;
int N, K, MOD;
 
struct SEG {
	SEG() { init(); }
	int d[MX*2];
	void init() { fill(d, d+MX*2, 1); }
	void upd(int s, int e, int x) {
		x %= MOD; if(1 == x) return;
		for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
			if(s&1) { d[s] = d[s] * x % MOD; s++; }
			if(~e&1) { d[e] = d[e] * x % MOD; e--; }
		}
	}
	int get(int x) {
		int r = 1; for(x += MX; x; x /= 2)
			r = r * d[x] % MOD;
		return r;
	}
} seg;
struct SEGT {
	SEGT() { init(); }
	int d[MX*2];
	void init() { fill(d, d+MX*2, 1); }
	void upd(int x, int r) {
		x += MX; d[x] = r;
		for(x /= 2; x; x /= 2)
			d[x] = d[x*2] * d[x*2+1] % MOD;
	}
	int get(int s, int e) {
		int r = 1; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
			if(s&1) {
				r = r * d[s] % MOD;
				s++;
			}
			if(~e&1) {
				r = r * d[e] % MOD;
				e--;
			}
		}
		return r;
	}
} segt;
 
int f(int i, int j) {
	return (int)(upper_bound(allv(BV[j]), C[i]/2) - BV[j].begin());
}
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N >> K >> MOD;
	for(int i = 1; i <= N; i++) cin >> B[i] >> A[i];
 
	for(int i = 1; i <= N; i++)
		upmax(C[A[i]], B[i]);
 
	iota(O, O+K+1, 0);
	sort(O+1, O+K+1, [&](int a, int b) {
		return C[a] > C[b];
	});
	for(int i = 1; i <= K; i++) RO[O[i]] = i;
 
	fill(C, C+K+1, 0);
	for(int i = 1; i <= N; i++) {
		A[i] = RO[A[i]];
		upmax(C[A[i]], B[i]);
		BV[A[i]].eb(B[i]);
	}
	for(int i = 1; i <= K; i++) sorv(BV[i]);
 
 
	{
		vector<int> V;
		for(int i = 1; i <= K; i++) {
			V.eb(C[i]);
			V.eb(C[i]/2);
		}
		for(int i = 1; i <= N; i++) V.eb(B[i]);
		sorv(V); univ(V);
		for(int i = 1; i <= K; i++) {
			CI[i] = (int)(lower_bound(allv(V), C[i]) - V.begin());
			CHI[i] = (int)(lower_bound(allv(V), C[i]/2) - V.begin());
		}
		for(int i = 1; i <= N; i++) {
			BI[i] = (int)(lower_bound(allv(V), B[i]) - V.begin());
			BIV[A[i]].eb(BI[i]);
		}
	}
	
	for(int i = 1; i <= K; i++) sorv(BIV[i]);
 
	for(int i = K; i; i--) {
		int ret = seg.get(CHI[i]);
		Ans = (Ans + f(i, i) % MOD * ret) % MOD;
 
		if(1 == i || f(i-1, i) != f(i, i)) {
			Ans = (Ans + ret) % MOD;
		} else {
			int s = 1, e = i-1; for(int m; s < e;) {
				m = (s+e)/2;
				if(f(m, i) == f(i, i)) e = m;
				else s = m+1;
			}
			QV[i] = pii(s, ret);
		}
 
		for(int j = 1; j < sz(BIV[i]); j++)
			seg.upd(BIV[i][j-1], BIV[i][j]-1, j+1);
		seg.upd(BIV[i].back(), MX-1, sz(BIV[i])+1);
	}
 
	priority_queue<pair<int, pii>> PQ;
	for(int i = 1; i <= K; i++) {
		int X = CHI[i], bi = -1;
 
		for(int j = 1; j < sz(BIV[i]); j++) {
			if(X < BIV[i][j-1]) continue;
			bi = j;
		}
		if(BIV[i].back() <= X) bi = sz(BIV[i]);
 
		if(1 <= bi) {
			segt.upd(i, bi+1);
			if(bi) PQ.push(pair<int, pii>(BIV[i][bi-1]-1, pii(i, bi)));
		}
 
		for(; !PQ.empty();) {
			int x, j, bj;
			x = PQ.top().first;
			tie(j, bj) = PQ.top().second;
 
			if(x < X) break;
			PQ.pop();
			segt.upd(j, 1);
			bj--;
			if(!bj) continue;
			segt.upd(j, bj+1);
			PQ.push(pair<int, pii>(BIV[j][bj-1]-1, pii(j, bj)));
		}
 
		if(!QV[i].first) continue;
 
		int v = QV[i].first;
		int ret = segt.get(v, i-1);
		ret = ret * QV[i].second % MOD;
		Ans = (Ans + ret) % MOD;
	}
 
	cout << Ans << endl;
	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: 0 / 5
• Subtask 19: 0 / 5