oj.uz

Submission #54686

# Submission time Handle Problem Language Result Execution time Memory
54686 2018-07-04T15:22:46 Z SpaimaCarpatilor Fish (IOI08_fish) C++17
58 / 100
 616 ms 61840 KB 
#include<bits/stdc++.h>

using namespace std;

const int maxN = 500000;
int N, K, mod, l[maxN + 9], t[maxN + 9], f[maxN + 9], lastCovered[maxN + 9];

void read ()
{
    scanf ("%d %d %d", &N, &K, &mod);
    vector < pair < int, int > > v;
    v.resize (N);
    for (int i=0; i<N; i++)
        scanf ("%d %d", &v[i].first, &v[i].second);
    sort (v.begin (), v.end ());
    for (int i=1; i<=N; i++)
        l[i] = v[i - 1].first, t[i] = v[i - 1].second;
}

namespace segtree {
    int aint[1100009];
    void build (int nod, int st, int dr)
    {
        aint[nod] = 1;
        if (st == dr) return ;
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        build (f1, st, mij);
        build (f2, mij + 1, dr);
    }

    void change (int nod, int st, int dr, int pos, int val)
    {
        if (st == dr)
        {
            aint[nod] = val % mod;
            return ;
        }
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        if (pos <= mij) change (f1, st, mij, pos, val);
        else change (f2, mij + 1, dr, pos, val);
        aint[nod] = (aint[f1] * aint[f2]) % mod;
    }

    int ansQ;
    void query (int nod, int st, int dr, int x, int y)
    {
        if (x <= st && dr <= y)
        {
            ansQ = (ansQ * aint[nod]) % mod;
            return ;
        }
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        if (x <= mij) query (f1, st, mij, x, y);
        if (mij < y) query (f2, mij + 1, dr, x, y);
    }

    int prod (int st, int dr)
    {
        ansQ = 1, dr = min (dr, N), st = max (st, 1);
        if (st <= dr) query (1, 1, N, st, dr);
        return ansQ;
    }
}

int minJ[maxN + 9], lst[maxN + 9], nxt[maxN + 9];
void buildMinJ ()
{
    int j = 0;
    for (int i=1; i<=N; i++)
    {
        while (j <= N && l[j] < 2 * l[i]) j ++;
        minJ[i] = j;
    }
}

void buildNxtLst ()
{
    for (int i=1; i<=N; i++)
    {
        if (lst[t[i]] != 0)
            nxt[lst[t[i]]] = i;
        lst[t[i]] = i;
    }
}

int ans = 0;
void computeAnswer ()
{
    int i = 0;
    for (int j=1; j<=N; j++)
    {
        while (l[i + 1] * 2 <= l[j])
            i ++, f[t[i]] ++, lastCovered[t[i]] = i,
            segtree::change (1, 1, N, lst[t[i]], f[t[i]] + 1);
        if (lst[t[j]] == j)
        {
            ///I take the max frequency for t[i]
            int k = minJ[nxt[lastCovered[t[j]]]];
            ans = (ans + segtree::prod (1, j - 1) * segtree::prod (j + 1, k - 1)) % mod;
            ///I take any number of t[i], but the max frequency
            ans = (ans + f[t[j]] * segtree::prod (1, j - 1)) % mod;
        }
    }
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

read (), segtree::build (1, 1, N);
buildNxtLst ();
buildMinJ ();
computeAnswer ();
printf ("%d\n", ans);

return 0;
}

Compilation message

fish.cpp: In function 'void read()':
fish.cpp:10:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d", &N, &K, &mod);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:14:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d %d", &v[i].first, &v[i].second);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Output isn't correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 472 KB Output isn't correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 608 KB Output is correct
2 Correct 2 ms 608 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 289 ms 18540 KB Output is correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 18540 KB Output isn't correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18540 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 18540 KB Output is correct
2 Correct 187 ms 18540 KB Output is correct

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18540 KB Output is correct
2 Incorrect 5 ms 18540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 25440 KB Output is correct
2 Correct 344 ms 35120 KB Output is correct
3 Correct 302 ms 41912 KB Output is correct

Subtask #12
0 / 7.0

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

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 48680 KB Output is correct
2 Correct 313 ms 51760 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 51760 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 52068 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 52068 KB Output is correct
2 Correct 262 ms 60020 KB Output is correct

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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