oj.uz

Submission #763700

# Submission time Handle Problem Language Result Execution time Memory
763700 2023-06-22T16:07:04 Z Kripton Fish (IOI08_fish) C++14
4 / 100
 3000 ms 5760 KB 
#include <bits/stdc++.h>
using namespace std;

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

int k, m;

int recalc()
{
    int rez = 1;
    for(int i = 1; i <= k; i++)
        if(!checc[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])
        {
            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;
                vf[v[i].second]++;
            }
            else
                cate = (cate + recalc()) % m;
            checc[v[i].second] = 1;
        }
    }
    cout << cate;
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 241 ms 4160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 1784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 340 KB Output is correct
2 Incorrect 9 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 2596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 262 ms 4212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 2648 KB Output is correct
2 Incorrect 574 ms 4268 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1104 ms 3924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2568 ms 4356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 3800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3062 ms 4968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 4940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 5760 KB Time limit exceeded
2 Halted 0 ms 0 KB -