oj.uz

답안 #763645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763645 2023-06-22T14:48:26 Z Kripton Fish (IOI08_fish) C++14
4 / 100
 3000 ms 5876 KB 
#include <bits/stdc++.h>
using namespace std;

pair <int, int> v[500001];
int vf[500001], maxi[500001];
bitset <500001> checc, dezact;

int k, m;

int recalc()
{
    int rez = 1;
    for(int i = 1; i <= k; i++)
        if(!dezact[i])
            rez = 1LL * rez * (vf[i] + 1) % m;
    return rez;
}

int recalc_fara(int j)
{
    int rez = 1;
    for(int i = 1; i <= k; i++)
        if(i != j)
            rez = 1LL * rez * (vf[i] + 1) % m;
    return rez;
}

int main()
{
#ifdef HOME
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif // HOME
    int n;
    cin >> n >> k >> m;
    for(int i = 1; i <= n; i++)
        cin >> v[i].first >> v[i].second;
    sort(v + 1, v + n + 1);
    int j = 1;
    while(j <= n && 2 * v[j].first <= v[n].first)
        vf[v[j++].second]++;
    j--;
    for(int i = 1; i <= k; i++)
        maxi[i] = vf[i];
    int cate = 0;
    for(int i = n; i >= 1; i--)
    {
        while(j >= 1 && 2 * v[j].first > v[i].first)
            vf[v[j--].second]--;
        if(!checc[v[i].second])
        {
            checc[v[i].second] = 1;
            if(vf[v[i].second] == maxi[v[i].second])
            {
                cate = (cate + recalc_fara(v[i].second)) % m;
                vf[v[i].second]--;
            }
            cate = (cate + recalc()) % m;
            dezact[v[i].second] = 1;
            if(vf[v[i].second] == maxi[v[i].second] - 1)
                vf[v[i].second]++;
        }
        //cout << cate << " ";
    }
    cout << cate;
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3065 ms 3832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3073 ms 5092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3076 ms 5008 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3076 ms 5876 KB Time limit exceeded
2 Halted 0 ms 0 KB -