# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
53760 |
2018-07-01T06:54:02 Z |
윤교준(#1438) |
Fish (IOI08_fish) |
C++11 |
|
3000 ms |
33912 KB |
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#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 = 7005;
const bool debug = 0;
int D[MAXK][MAXK];
int C[MAXK], O[MAXK], RO[MAXK];
int A[MAXN], B[MAXN];
ll Ans;
int N, K, MOD;
int main() {
ios::sync_with_stdio(false);
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]);
}
for(int i = 1; i <= K; i++) {
for(int j = 1; j <= N; j++)
if(B[j]*2 <= C[i])
D[i][A[j]]++;
}
if(debug) {
for(int i = 1; i <= K; i++) printf("%d : %d\n", i, C[i]);
for(int i = 1; i <= K; i++) {
for(int j = 1; j <= K; j++)
printf("%d ", D[i][j]);
puts("");
}
}
fill(D[0], D[0]+K+1, -1);
for(int i = 1; i <= K; i++) {
if(!C[i]) continue;
ll ret = 0;
if(1 == i || D[i][i]) {
ret = D[i][i] + (1 == i);
for(int j = i+1; j <= K; j++)
ret = ret * (D[i][j] + 1) % MOD;
Ans = (Ans + ret) % MOD;
if(debug) printf("T1 %d : %lld\n", i, ret);
} else if(D[i][i] != D[i-1][i]) {
ret = 1;
for(int j = i+1; j <= K; j++)
ret = ret * (D[i][j] + 1) % MOD;
Ans = (Ans + ret) % MOD;
if(debug) printf("T11 %d : %lld\n", i, ret);
}
if(D[i][i] == D[i-1][i]) {
ret = 1;
for(int j = i+1; j <= K; j++)
ret = ret * (D[i][j] + 1) % MOD;
for(int j = 1; j < i; j++)
if(D[j][i] == D[i][i])
ret = ret * (D[i][j] + 1) % MOD;
Ans = (Ans + ret) % MOD;
if(debug) printf("T2 %d : %lld\n", i, ret);
}
}
cout << Ans << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
620 KB |
Output is correct |
2 |
Correct |
3 ms |
676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
696 KB |
Output is correct |
2 |
Correct |
182 ms |
4592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
4592 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
4592 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
374 ms |
4592 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
93 ms |
4592 KB |
Output is correct |
2 |
Incorrect |
71 ms |
8684 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3052 ms |
19344 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1552 ms |
28236 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3042 ms |
28236 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3038 ms |
33912 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
136 ms |
33912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
288 ms |
33912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1984 ms |
33912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1401 ms |
33912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3054 ms |
33912 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |