oj.uz

답안 #1025121

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1025121 2024-07-16T16:16:04 Z vjudge1 Fish (IOI08_fish) C++17
100 / 100
 669 ms 32924 KB 
#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair < int, int >

using namespace std;

const int N = 5e5+10, K = 5e5+10;
const int logN = 20, maxN = (1<<20), startpos = maxN-1;
int n, k, m;
pii ribe[N];
int najvecidrag[K];
int draginterval[K];
int cur;
int lowout[K];
int st[maxN<<1];
vector < int > dragulji;
int sol;
bool rip[K];
//bool ripp[7010][7010];
int temp;
int newcol[K];
int granice[K];

bool dragsort1( int a, int b ) {
	if(najvecidrag[a] > najvecidrag[b]) return 1;
	return 0;
}

bool dragsort2( int a, int b ) {
	if(lowout[a] > lowout[b]) return 1;
	return 0;
}

int add( int a, int b ) {
	return (a + b >= m) ? a+b-m : a+b;
}

int mul( int a, int b ) {
	return (ll) a * b % m;
}

inline void merge( int i ) {
	st[i] = mul(st[i*2+1], st[i*2+2]);
	return;
}

inline void update( int i, int v ) {
	
	i += startpos;
	st[i] += v;
	while(i != 0) {
		i = (i - 1) / 2;
		merge(i);
	}
	return;
	
}

int product( int i, int l, int r, int lo, int hi ) {
	if(l>=lo && r<=hi) return st[i];
	if(r<=lo || l>=hi) return 1;
	return mul(product(i*2+1, l, l + (r - l) / 2, lo, hi), product(i*2+2, l + (r - l) / 2, r, lo, hi));
}

int main( void ) {
	
	FIO
	cin >> n >> k >> m;
	for(int i = 0; i < n; i++) {
		cin >> ribe[i].F >> ribe[i].S;
		ribe[i].S--;
	}
	sort(ribe, ribe + n);
	cur = 0;
	for(int i = 0; i < n; i++) {
		najvecidrag[ribe[i].S] = i;
	}
	for(int i = 0; i < k; i++) dragulji.pb(i);
	sort(dragulji.begin(), dragulji.end(), dragsort1);
	reverse(dragulji.begin(), dragulji.end());
	for(int i = 0; i < k; i++) {
		newcol[dragulji[i]] = i;
	}
	dragulji.clear();
	for(int i = 0; i < n; i++) {
		ribe[i].S = newcol[ribe[i].S];
	}
	for(int i = 0; i < n; i++) {
		najvecidrag[ribe[i].S] = i;
		while(ribe[cur].F * 2 <= ribe[i].F) {
			cur++;
		}
		draginterval[ribe[i].S] = cur;
		lowout[ribe[i].S] = n;
	}
	for(int i = 0; i < n; i++) {
		if(i >= draginterval[ribe[i].S]) {
			lowout[ribe[i].S] = min(lowout[ribe[i].S], i);
		}
	}
	for(int i = 0; i < maxN<<1; i++) st[i] = 1;
	for(int i = 0; i < n; i++) {
		update(ribe[i].S, 1);
	}
	for(int i = 0; i < k; i++) {
		dragulji.pb(i);
	}
	sort(dragulji.begin(), dragulji.end(), dragsort1);
	cur = n-1;
	for(int i = 0; i < k; i++) {
		while(cur >= 0 && draginterval[dragulji[i]] <= cur) {
			if(!rip[ribe[cur].S])update(ribe[cur].S, -1);
			cur--;
		}
//		cout << st[startpos+0] << " " << st[startpos+1] << " " << st[startpos+2] << " " << st[startpos+3] << "\n";
		update(dragulji[i], -1);
		sol = add(sol, st[0]);
		update(dragulji[i], 1-st[dragulji[i] + startpos]);
		rip[dragulji[i]] = 1;
//		cout << st[startpos+0] << " " << st[startpos+1] << " " << st[startpos+2] << " " << st[startpos+3] << "\n\n";
	}
	for(int i = 0; i < k; i++) rip[i] = 0;
//	cout << sol << "\n";
	cur = 0;
	for(int i = 0; i < k; i++) granice[i] = k;
	sort(dragulji.begin(), dragulji.end(), dragsort2);
	reverse(dragulji.begin(), dragulji.end());
	for(int i = 0; i < k; i++) {
		while(lowout[dragulji[cur]] < draginterval[i]) {
			granice[dragulji[cur]] = i;
			cur++;
		}
	}
	cur = n-1;
	sort(dragulji.begin(), dragulji.end(), dragsort1);
	for(int i = 0; i < maxN<<1; i++) st[i] = 1;
	for(int i = 0; i < n; i++) {
		update(ribe[i].S, 1);
	}
//
	for(int i = 0; i < k; i++) {
		while(cur >= 0 && draginterval[dragulji[i]] <= cur) {
			update(ribe[cur].S, -1);
			cur--;
		}
		temp = 1 - st[dragulji[i] + startpos];
		update(dragulji[i], temp);
		sol = add(sol, product(0, 0, maxN, 0, granice[dragulji[i]]));
//		cout << product(0, 0, maxN, 0, granice[i]) << "\n";
		update(dragulji[i], -temp);
	}
//	cout << "\n";
//	for(int i = 0; i < n; i++) cout << ribe[i].F << " " << ribe[i].S << "\n";
//
	
	cout << sol;
	
	return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8540 KB Output is correct
2 Correct 6 ms 8540 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8540 KB Output is correct
2 Correct 295 ms 18856 KB Output is correct

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 12624 KB Output is correct
2 Correct 136 ms 13652 KB Output is correct

Subtask #10
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8792 KB Output is correct
2 Correct 9 ms 8796 KB Output is correct
3 Correct 8 ms 8852 KB Output is correct

Subtask #11
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 142 ms 14932 KB Output is correct
2 Correct 274 ms 19352 KB Output is correct
3 Correct 273 ms 19140 KB Output is correct

Subtask #12
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 18692 KB Output is correct
2 Correct 246 ms 19540 KB Output is correct

Subtask #13
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 15276 KB Output is correct
2 Correct 251 ms 19572 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 250 ms 19160 KB Output is correct
2 Correct 378 ms 22800 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 397 ms 22984 KB Output is correct
2 Correct 319 ms 19340 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 373 ms 21192 KB Output is correct
2 Correct 388 ms 22768 KB Output is correct
3 Correct 400 ms 24016 KB Output is correct
4 Correct 380 ms 22732 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 463 ms 25552 KB Output is correct
2 Correct 634 ms 32052 KB Output is correct
3 Correct 664 ms 32924 KB Output is correct
4 Correct 669 ms 30412 KB Output is correct