oj.uz

Submission #763702

# Submission time Handle Problem Language Result Execution time Memory
763702 2023-06-22T16:14:00 Z Kripton Fish (IOI08_fish) C++14
4 / 100
 3000 ms 5784 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++;
    }
    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]--;
            j--;
        }
        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 0 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 4140 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 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 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 96 ms 1860 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 356 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 2588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 2744 KB Output is correct
2 Incorrect 559 ms 4272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2541 ms 4360 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 3022 ms 3928 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 3073 ms 4940 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 3042 ms 5008 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 3053 ms 5784 KB Time limit exceeded
2 Halted 0 ms 0 KB -