Submission #74879

# Submission time Handle Problem Language Result Execution time Memory
74879 2018-09-07T09:01:25 Z Alexa2001 Fish (IOI08_fish) C++17
63 / 100
650 ms 66560 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];
            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];
            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]];
            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:81:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(step = 1; step <= k; step<<=1); step >>= 1;
     ^~~
fish.cpp:81: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;
                                         ^~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 652 KB Output is correct
2 Correct 208 ms 22416 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 22416 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 22416 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 95 ms 22416 KB Output is correct
2 Correct 107 ms 22416 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 22416 KB Output is correct
2 Correct 6 ms 22416 KB Output is correct
3 Correct 6 ms 22416 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 146 ms 26080 KB Output is correct
2 Incorrect 255 ms 39124 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 312 ms 45096 KB Output is correct
2 Correct 251 ms 52184 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 154 ms 52184 KB Output is correct
2 Correct 250 ms 63568 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 238 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
# Verdict Execution time Memory Grader output
1 Runtime error 324 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
# Verdict Execution time Memory Grader output
1 Runtime error 254 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 580 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 399 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 650 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -