oj.uz

Submission #54695

# Submission time Handle Problem Language Result Execution time Memory
54695 2018-07-04T16:05:41 Z SpaimaCarpatilor Fish (IOI08_fish) C++17
100 / 100
 775 ms 24636 KB 
#include<bits/stdc++.h>

using namespace std;

const int maxN = 1000000;
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 {
    short 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] = ((int) 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], frst[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 buildNxtLstFrst ()
{
    for (int i=1; i<=N; i++)
    {
        if (lst[t[i]] != 0)
            nxt[lst[t[i]]] = i;
        lst[t[i]] = i;
    }
    for (int i=N; i>=1; i--)
        frst[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]]]];
            if (k == 0) k = minJ[frst[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]] % mod) * segtree::prod (1, j - 1)) % mod;
        }
    }
}

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

read (), segtree::build (1, 1, N);
buildNxtLstFrst ();
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 484 KB Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 10388 KB Output is correct
2 Correct 170 ms 10388 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10388 KB Output is correct
2 Correct 5 ms 10388 KB Output is correct
3 Correct 6 ms 10388 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 10388 KB Output is correct
2 Correct 388 ms 10536 KB Output is correct
3 Correct 350 ms 10564 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 10564 KB Output is correct
2 Correct 311 ms 10664 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 10664 KB Output is correct
2 Correct 375 ms 10788 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 10788 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 10916 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 10916 KB Output is correct
2 Correct 280 ms 11300 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 12076 KB Output is correct
2 Correct 366 ms 12076 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 12076 KB Output is correct
2 Correct 441 ms 12332 KB Output is correct
3 Correct 567 ms 13540 KB Output is correct
4 Correct 542 ms 19872 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 21348 KB Output is correct
2 Correct 755 ms 24152 KB Output is correct
3 Correct 567 ms 24152 KB Output is correct
4 Correct 775 ms 24636 KB Output is correct