Submission #54695

#	Time	Username	Problem	Language	Result	Execution time	Memory
54695		SpaimaCarpatilor	Fish (IOI08_fish)	C++17	100 / 100	775 ms	24636 KiB

fish

#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 (stderr)

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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 7 / 7
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5