oj.uz

Submission #443337

# Submission time Handle Problem Language Result Execution time Memory
443337 2021-07-10T11:25:39 Z LittleCube Global Warming (CEOI18_glo) C++14
0 / 100
 27 ms 772 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

struct segTree
{
    int l[6000000], r[6000000], seg[6000000], rdx = 1;
    const ll mxL = -10, mxR = 1000000010;
    void modify(ll L, ll R, int i, int idx, int val)
    {
        if (L == R)
        {
            seg[i] = val;
            return;
        }
        int mid = (L + R) / 2;
        if (idx <= mid)
        {
            if (l[i] == 0)
                l[i] = ++rdx;
            modify(L, mid, l[i], idx, val);
        }
        else
        {
            if (r[i] == 0)
                r[i] = ++idx;
            modify(mid + 1, R, r[i], idx, val);
        }
        seg[i] = max((l[i] == 0 ? 0 : seg[l[i]]), (r[i] == 0 ? 0 : seg[r[i]]));
    }

    void modify(int idx, int val)
    {
        modify(mxL, mxR, 1, idx, val);
    }

    int query(ll L, ll R, int i, ll qL, ll qR)
    {
        if (qL <= L && R <= qR)
            return seg[i];
        if (qR < L || R < qL)
            return 0;
        int mid = (L + R) / 2;
        return max((l[i] == 0 ? 0 : query(L, mid, l[i], qL, qR)), (r[i] == 0 ? 0 : query(mid + 1, R, r[i], qL, qR)));
    }

    int query(ll qR)
    {
        return query(mxL, mxR, 1, mxL, qR);
    }
};

ll N, x;
segTree nmod, mod[12], moded;
ll nmoddp[200005], moddp[200005][12], modeddp[200005];

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> x;
    for (int i = 1; i <= N; i++)
    {
        ll k;
        cin >> k;
        for (int j = 1; j <= x; j++)
            modeddp[i] = max(modeddp[i], mod[j].query(k - 1)) + 1;
        for (int j = 1; j <= x; j++)
            modeddp[i] = max(modeddp[i], mod[5 + j].query(k - 1)) + 1;
        modeddp[i] = max(modeddp[i], moded.query(k - 1)) + 1;

        moded.modify(k, modeddp[i]);

        for (int j = 1; j <= x; j++)
        {
            moddp[i][j] = max(nmod.query(k - 1 - j), mod[j].query(k - 1 - j)) + 1;
            mod[j].modify(k - j, moddp[i][j]);
        }
        for (int j = 1; j <= x; j++)
        {
            moddp[i][j + 5] = max(nmod.query(k - 1 + j), mod[j].query(k - 1 + j)) + 1;
            mod[j].modify(k + j, moddp[i][j]);
        }

        nmoddp[i] = nmod.query(k - 1) + 1;
        nmod.modify(k, nmoddp[i]);
    }
    int ans = 0;
    ans = max(ans, nmod.query(1000000010));
    ans = max(ans, moded.query(1000000010));
    for (int i = 1; i <= x; i++)
        ans = max({ans, mod[i].query(1000000010), mod[i + 5].query(1000000010)});
    cout << ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 584 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -