oj.uz

Submission #157092

# Submission time Handle Problem Language Result Execution time Memory
157092 2019-10-09T12:59:48 Z youngyojun Fish (IOI08_fish) C++11
90 / 100
 985 ms 65536 KB 
#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.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 40268 KB Output is correct
2 Correct 43 ms 40312 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 40312 KB Output is correct
2 Correct 416 ms 53020 KB Output is correct

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 45992 KB Output is correct
2 Correct 232 ms 47460 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 40568 KB Output is correct
2 Correct 46 ms 40568 KB Output is correct
3 Correct 44 ms 40624 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 48988 KB Output is correct
2 Correct 503 ms 53652 KB Output is correct
3 Correct 454 ms 56040 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 54920 KB Output is correct
2 Correct 479 ms 57460 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 49496 KB Output is correct
2 Correct 512 ms 56480 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 53816 KB Output is correct
2 Correct 725 ms 65536 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 65536 KB Output is correct
2 Correct 668 ms 63872 KB Output is correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 65536 KB Output is correct
2 Correct 985 ms 65536 KB Output is correct
3 Runtime error 460 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 544 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -