Submission #74889

#	Time	Username	Problem	Language	Result	Execution time	Memory
74889		Alexa2001	Fish (IOI08_fish)	C++17	100 / 100	757 ms	34544 KiB

fish

#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

using namespace std;

const int Nmax = 5e5 + 5;

int Mod, Ans, n, i, k;
int prv[Nmax], nxt[Nmax], ord[Nmax], same[Nmax], go[Nmax], last[Nmax], F[Nmax], where[Nmax];
vector<int> Cnt, good;

struct fish
{
    int len, kind;
    bool operator < (const fish &other) const
    {
        return len < other.len;
    }
} a[Nmax];

class Aint
{
    int a[Nmax<<2];
public:
    void build(int node, int st, int dr)
    {
        if(st == dr)
        {
            a[node] = Cnt[st-1] % Mod;
            return;
        }

        build(left_son, st, mid);
        build(right_son, mid+1, dr);
        a[node] = a[left_son] * a[right_son] % Mod;
    }

    void query(int node, int st, int dr, int L, int R)
    {
        if(L <= st && dr <= R)
        {
            Ans *= a[node];
            Ans %= Mod;
            return;
        }
        if(L <= mid) query(left_son, st, mid, L, R);
        if(mid < R) query(right_son, mid+1, dr, L, R);
    }

    void update(int node, int st, int dr, int pos)
    {
        if(st == dr)
        {
            --a[node];
            if(a[node] == -1) a[node] = Mod-1;
            return;
        }
        if(pos <= mid) update(left_son, st, mid, pos);
            else update(right_son, mid+1, dr, pos);
        a[node] = a[left_son] * a[right_son] % Mod;
    }
} Weee;

int Query(int x, int y)
{
    Ans = 1; x = max(x, 0); y = min(y, k-1);
    if(x <= y) Weee.query(1, 1, k, x+1, y+1);
    return Ans;
}

void Decr(int x)
{
    Weee.update(1, 1, k, x+1);
    -- Cnt[x];
}

int Search(int x)
{
    int step, ans = 0;
    for(step = 1; step <= k; step<<=1); step >>= 1;

    for(; step; step>>=1)
        if(ans + step < k && go[good[ans + step]] < x) ans += step;
    return ans;
}

void solve()
{
    int i, pos, ans = 0;
    for(i=1; i<=n; ++i)
        if(!nxt[i]) where[a[i].kind] = good.size(), good.push_back(i), Cnt.push_back(ord[i] + 1);
    Weee.build(1, 1, k);

    int id = k, j = n;
    for(i=n; i; --i)
        if(!nxt[i])
        {
            --id;

            while(2 * a[j].len > a[i].len)
            {
                Decr(where[a[j].kind]);
                --j;
            }

            if(same[i]) pos = Search(nxt[same[i]]);
                else pos = Search(F[i]);

            ans += Query(0, id-1) * Query(id+1, pos);
            ans += Query(0, id-1) * (ord[same[i]] % Mod);
            ans %= Mod;
        }

    cout << ans << '\n';
}

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

    cin.sync_with_stdio(false);

    cin >> n >> k >> Mod;
    for(i=1; i<=n; ++i) cin >> a[i].len >> a[i].kind;
    sort(a+1, a+n+1);

    for(i=1; i<=n; ++i)
    {
        go[i] = go[i-1];
        while(2 * a[go[i] + 1].len <= a[i].len) ++ go[i];
    }

    for(i=1; i<=n; ++i)
    {
        prv[i] = last[a[i].kind];
        nxt[last[a[i].kind]] = i;
        last[a[i].kind] = i;
        ord[i] = ord[prv[i]] + 1;

        if(!prv[i]) F[i] = i;
            else F[i] = F[prv[i]];

        same[i] = same[prv[i]];
        if(!same[i])
        {
            if(go[i] >= F[i]) same[i] = F[i];
                else continue;
        }

        while(go[i] >= nxt[same[i]]) same[i] = nxt[same[i]];
    }

    solve();
    return 0;
}

Compilation message (stderr)

fish.cpp: In function 'int Search(int)':
fish.cpp:82:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(step = 1; step <= k; step<<=1); step >>= 1;
     ^~~
fish.cpp:82:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(step = 1; step <= k; step<<=1); step >>= 1;
                                         ^~~~

• 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