oj.uz

답안 #53805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53805 2018-07-01T08:32:28 Z 윤교준(#1438) Fish (IOI08_fish) C++11
38 / 100
 3000 ms 196608 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#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 bool debug = 0;
static unsigned char str[55000055], *p=str;

const int MAXN = 500005;
const int MAXK = 500005;
const int MX = 1048576;

vector<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 NOD {
	NOD() : l(NULL), r(NULL), dt(1) {}
	NOD *l, *r;
	int dt;
	void upd(int s, int e, int p, int q, int x) {
		if(q < p || e < p || q < s) return;
		if(p <= s && e <= q) {
			dt = dt * x % MOD;
			return;
		}
		int m = (s+e)/2;
		if(p <= m) {
			if(NULL == l) l = new NOD();
			l -> upd(s, m, p, q, x);
		}
		if(m < q) {
			if(NULL == r) r = new NOD();
			r -> upd(m+1, e, p, q, x);
		}
	}
	int get(int s, int e, int x) {
		int m = (s+e)/2;
		if(x <= m) {
			if(NULL == l) return dt;
			return dt * (l -> get(s, m, x)) % MOD;
		} else {
			if(NULL == r) return dt;
			return dt * (r -> get(m+1, e, x)) % MOD;
		}
	}
};
struct DYSEG {
	NOD nod[MX*2];
	void upd(int c, int s, int e, int x) {
		x %= MOD; if(1 == x || e < s) return;
		for(c += MX; c; c /= 2)
			nod[c].upd(0, MX-1, s, e, x);
	}
	int get(int s, int e, int x) {
		int r = 1; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
			if(s&1) {
				r = r * nod[s].get(0, MX-1, x) % MOD;
				s++;
			}
			if(~e&1) {
				r = r * nod[e].get(0, MX-1, x) % MOD;
				e--;
			}
		}
		return r;
	}
} dyseg;

int f(int i, int j) {
	return (int)(upper_bound(allv(BV[j]), C[i]/2) - BV[j].begin());
}

int main() {
	fread(str, 1, 55000055, stdin);

	rf(N) rf(K) rf(MOD)
	for(int i = 1; i <= N; i++) { rf(B[i]) rf(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]].pb(B[i]);
	}
	for(int i = 1; i <= K; i++) sorv(BV[i]);


	{
		vector<int> V;
		for(int i = 1; i <= K; i++) {
			V.pb(C[i]);
			V.pb(C[i]/2);
		}
		for(int i = 1; i <= N; i++) V.pb(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]].pb(BI[i]);
		}
	}
	
	for(int i = 1; i <= K; i++) sorv(BIV[i]);

	if(debug) {
		for(int i = 1; i <= K; i++) {
			for(int j = 1; j <= K; j++)
				printf("%d ", f(i, j));
			puts("");
		}
	}

	for(int i = K; i; i--) {
		int ret = seg.get(CHI[i]);
		Ans = (Ans + f(i, i) % MOD * ret) % MOD;
		if(debug) printf("T1 %d : %d\n", i, f(i, i) % MOD * ret % MOD);

		if(1 == i || f(i-1, i) != f(i, i)) {
			Ans = (Ans + ret) % MOD;
			if(debug) printf("T2 %d : %d\n", i, ret);
		} 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[s].eb(i, ret);
			if(debug) printf("Q i=%d, s=%d, ret=%d\n", i, 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);
	}

	for(int i = K; i; i--) {
		for(int j = 1; j < sz(BIV[i]); j++)
			dyseg.upd(i, BIV[i][j-1], BIV[i][j]-1, j+1);
		dyseg.upd(i, BIV[i].back(), MX-1, sz(BIV[i])+1);

		for(pii v : QV[i]) {
			int j = v.first;
			int t = dyseg.get(i, j-1, CHI[j]);
			t = t * v.second % MOD;
			Ans = (Ans + t) % MOD;
			if(debug) printf("T2 i=%d, %d : %d :: (%d, %d)\n", i, j, t, v.first, v.second);
		}
	}

	cout << Ans << endl;
	return 0;
}

Compilation message

fish.cpp: In function 'int main()':
fish.cpp:109:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 55000055, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 93048 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 93196 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 93320 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 93320 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 94264 KB Output is correct
2 Correct 78 ms 94968 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 94968 KB Output is correct
2 Execution timed out 2732 ms 196608 KB Time limit exceeded (wall clock)

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 196608 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 196608 KB Output is correct

Subtask #9
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2983 ms 196608 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #10
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 196608 KB Output is correct
2 Correct 148 ms 196608 KB Output is correct
3 Correct 121 ms 196608 KB Output is correct

Subtask #11
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2955 ms 196608 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 196608 KB Output is correct
2 Execution timed out 2974 ms 196608 KB Time limit exceeded (wall clock)

Subtask #13
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1623 ms 196608 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3047 ms 196608 KB Time limit exceeded

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3024 ms 196608 KB Time limit exceeded

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2054 ms 196608 KB Output is correct
2 Runtime error 2831 ms 196608 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2470 ms 196608 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2635 ms 196608 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2922 ms 196608 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -