oj.uz

답안 #53800

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53800 2018-07-01T08:20:01 Z 김세빈(#1437) Fish (IOI08_fish) C++11
4 / 100
 885 ms 28156 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

int T[1101010];
vector <int> V[505050];
int M[505050], K[505050], D[505050], C[505050];
bool chk[505050];
pii F[505050];
int n, k, m, sz, ans;

void update(int p, int v)
{
	p += sz;
	T[p] = v % m;
	
	for(p>>=1;p;p>>=1){
		T[p] = (T[p<<1] * T[p<<1|1]) % m;
	}
}

int get_mult(int l, int r)
{
	int ret = 1;
	l += sz, r += sz;
	
	for(;l<r;){
		if(l & 1) ret = (ret * T[l]) % m;
		if(~r & 1) ret = (ret * T[r]) % m;
		l = l+1 >> 1;
		r = r-1 >> 1;
	}
	if(l == r) ret = (ret * T[l]) % m;
	
	return ret;
}

bool comp(int ca, int cb) { return M[ca] < M[cb]; }

int main()
{
//	freopen("input.txt","r",stdin);
	
	int i, j, a, b;
	int s, e, mid;
	
	scanf("%d%d%d", &n, &k, &m);
	
	for(i=0;i<n;i++){
		scanf("%d%d", &a, &b); b--;
		F[i] = pii(a, b);
		V[b].push_back(a);
		M[b] = max(M[b], a);
	}
	
	sort(F, F+n);
	
	for(sz=1;sz<k;sz<<=1);
	for(i=1;i<sz+k;i++) T[i] = 1;
	
	for(i=0;i<k;i++) D[i] = i;
	sort(D, D+k, comp);
	for(i=0;i<k;i++) K[D[i]] = i;
	
	for(i=j=0;i<n;i++){
		for(;j<n && F[j].first * 2 <= F[i].first; j++){
			C[F[j].second] ++;
			update(K[F[j].second], C[F[j].second] + 1);
		}
		
		b = F[i].second;
	
		if(F[i].first == M[b] && !chk[b]){
			chk[b] = 1;
			
			for(s=K[b]+1,e=k-1;s<=e;){
				mid = s+e >> 1;
				if(upper_bound(V[b].begin(), V[b].end(), M[K[mid]]/2) - V[b].begin() <= C[b]) s = mid+1;
				else e = mid-1;
			}
			
			update(K[b], 1);
			ans = (ans + get_mult(0, s-1) + get_mult(0, K[b]) * C[b]) % m;
//			printf("%d %d %d %d\n", b, s-1, get_mult(0, s-1), get_mult(0, K[b]) * C[b]);
			update(K[b], C[b] + 1);
		}
	}
	
	printf("%d\n",ans);
	
	return 0;
}

Compilation message

fish.cpp: In function 'int get_mult(int, int)':
fish.cpp:32:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   l = l+1 >> 1;
       ~^~
fish.cpp:33:8: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   r = r-1 >> 1;
       ~^~
fish.cpp: In function 'int main()':
fish.cpp:79:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mid = s+e >> 1;
           ~^~
fish.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fish.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b); b--;
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 12392 KB Output isn't correct

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 12392 KB Output isn't correct

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 12400 KB Output isn't correct

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12428 KB Output is correct
2 Incorrect 12 ms 12488 KB Output isn't correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12488 KB Output is correct
2 Incorrect 241 ms 19048 KB Output isn't correct

Subtask #7
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 19048 KB Output isn't correct

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 19048 KB Output isn't correct

Subtask #9
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 102 ms 19048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 19048 KB Output is correct
2 Incorrect 18 ms 19048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 178 ms 19048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 257 ms 19512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 19512 KB Output is correct
2 Incorrect 291 ms 19512 KB Output isn't correct

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 276 ms 19512 KB Output isn't correct

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 372 ms 20368 KB Output isn't correct

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 381 ms 20368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 724 ms 25304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 583 ms 26600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 885 ms 28156 KB Output isn't correct
2 Halted 0 ms 0 KB -