oj.uz

Submission #53836

# Submission time Handle Problem Language Result Execution time Memory
53836 2018-07-01T09:14:28 Z 윤교준(#1438) Fish (IOI08_fish) C++11
100 / 100
 1446 ms 101596 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;

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() {
	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[i] = pii(s, 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);
	}

	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;
			//PQ.push(EVT(i, BIV[i][j-1], BIV[i][j]-1, j+1));
		}
		if(BIV[i].back() <= X) bi = sz(BIV[i]);
		//PQ.push(EVT(i, BIV[i].back(), MX-1, sz(BIV[i])+1));

		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;
	}

/*
	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:80: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

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 40332 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 40408 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 40448 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 40504 KB Output is correct
2 Correct 33 ms 40504 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 40504 KB Output is correct
2 Correct 319 ms 59436 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 59436 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 59436 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 59436 KB Output is correct
2 Correct 174 ms 59436 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 59436 KB Output is correct
2 Correct 38 ms 59436 KB Output is correct
3 Correct 36 ms 59436 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 59436 KB Output is correct
2 Correct 412 ms 59788 KB Output is correct
3 Correct 345 ms 61016 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 61016 KB Output is correct
2 Correct 360 ms 61688 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 61688 KB Output is correct
2 Correct 400 ms 61688 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 61688 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 62944 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 62944 KB Output is correct
2 Correct 660 ms 68324 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 69060 KB Output is correct
2 Correct 710 ms 69060 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 69472 KB Output is correct
2 Correct 870 ms 69472 KB Output is correct
3 Correct 786 ms 75544 KB Output is correct
4 Correct 848 ms 75544 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 948 ms 75544 KB Output is correct
2 Correct 1072 ms 100632 KB Output is correct
3 Correct 1446 ms 101596 KB Output is correct
4 Correct 1290 ms 101596 KB Output is correct