oj.uz

Submission #74889

# Submission time Handle Problem Language Result Execution time Memory
74889 2018-09-07T09:41:54 Z Alexa2001 Fish (IOI08_fish) C++17
100 / 100
 757 ms 34544 KB 
#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

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.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 500 KB Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 756 KB Output is correct
2 Correct 204 ms 16228 KB Output is correct

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 16228 KB Output is correct
2 Correct 111 ms 16228 KB Output is correct

Subtask #10
6.0 / 6.0

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

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 16228 KB Output is correct
2 Correct 271 ms 16412 KB Output is correct
3 Correct 274 ms 16412 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 16412 KB Output is correct
2 Correct 267 ms 16416 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 16416 KB Output is correct
2 Correct 275 ms 16648 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 16648 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 17020 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 17020 KB Output is correct
2 Correct 441 ms 19056 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 19428 KB Output is correct
2 Correct 391 ms 19428 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 19428 KB Output is correct
2 Correct 495 ms 19428 KB Output is correct
3 Correct 467 ms 21352 KB Output is correct
4 Correct 540 ms 26736 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 29532 KB Output is correct
2 Correct 757 ms 34280 KB Output is correct
3 Correct 700 ms 34280 KB Output is correct
4 Correct 745 ms 34544 KB Output is correct