Submission #1069871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069871		danikoynov	Financial Report (JOI21_financial)	C++17	100 / 100	1778 ms	50136 KiB

Main

#include<bits/stdc++.h>

using namespace std;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

const int MAXN = 3e5 + 10;

struct Node
{
    int lon, pref, suff, len;

    Node()
    {
        lon = pref = suff = len = 0;
    }
};

Node tree[4 * MAXN];

Node unite(Node lf, Node rf)
{
    if (lf.len == 0)
        return rf;
    if (rf.len == 0)
        return lf;
    Node mf;
    mf.lon = max(lf.lon, rf.lon);
    mf.lon = max(mf.lon, lf.suff + rf.pref);
    mf.len = lf.len + rf.len;
    mf.pref = lf.pref;
    mf.suff = rf.suff;
    if (lf.pref == lf.len)
        mf.pref = lf.len + rf.pref;
    if (rf.suff == rf.len)
        mf.suff = rf.len + lf.suff;
    return mf;
}

void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root].lon = 1;
        tree[root].pref = tree[root].suff = 1;
        tree[root].len = 1;
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = unite(tree[root * 2], tree[root * 2 + 1]);
}

void toggle(int root, int left, int right, int pivot)
{
    if (left == right)
    {
        tree[root].lon = 0;
        tree[root].pref = tree[root].suff = 0;
        tree[root].len = 1;
        return;
    }

    int mid = (left + right) / 2;
    if (pivot <= mid)
        toggle(root * 2, left, mid, pivot);
    else
        toggle(root * 2 + 1, mid + 1, right, pivot);

    tree[root] = unite(tree[root * 2], tree[root * 2 + 1]); 
}

Node query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return Node();
    
    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;
    return unite(query(root * 2, left, mid, qleft, qright),
            query(root * 2 + 1, mid + 1, right, qleft, qright));
}

int n, a[MAXN], d, dp[MAXN];
pair < int, int > val[MAXN];
int to[MAXN], rev[MAXN];

int ch_tree[4 * MAXN];
void update(int root, int left, int right, int pivot, int val)
{
    if (left == right)
    {
        ch_tree[root] = val;
        return;
    }

    int mid = (left + right) / 2;
    if (pivot <= mid)
        update(root * 2, left, mid, pivot, val);
    else
        update(root * 2 + 1, mid + 1, right, pivot, val);
    
    ch_tree[root] = max(ch_tree[root * 2], ch_tree[root * 2 + 1]);
}

int ch_query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return 0;
    if (left >= qleft && right <= qright)
        return ch_tree[root];

    int mid = (left + right) / 2;
    return max(ch_query(root * 2, left, mid, qleft, qright),
            ch_query(root * 2 + 1, mid + 1, right, qleft, qright));
}

vector < int > task[MAXN];

void solve()
{
    cin >> n >> d;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        val[i] = {a[i], -i};
    }


    sort(val + 1, val + n + 1);
    build_tree(1, 1, n);
    for (int i = 1; i <= n; i ++)
    {
        int id =  - val[i].second;
        rev[id] = i;
        toggle(1, 1, n, id);
        int l = id - 1, r = n + 1;
        while(l + 1 < r)
        {
            //cout << "here " << l << " : " << r << endl;
            int m = (l + r) / 2;
            Node cur = query(1, 1, n, id, m);
            //cout << "lon " << cur.lon << endl;

            if (cur.lon >= d)
                r = m;
            else
                l = m;
        }


        //cout << id << " : " << l + 1 << endl;
        to[id] = l + 1;
        if (to[id] > n)
            to[id] = n;
    }
    int res = 0;
    for (int i = 1; i <= n; i ++)
    {
        for (int cur : task[i])
        {
            update(1, 1, n, rev[cur], 0);
        }
        dp[i] = ch_query(1, 1, n, 1, rev[i]) + 1;
        if (i == n)
        {
            res = max(dp[i], ch_tree[1]);
        }   
        update(1, 1, n, rev[i], dp[i]);
        task[to[i] + 1].push_back(i);
        /*
        dp[i] = max(dp[i], 1);
        //int ls = i;
        for (int j = i + 1; j <= to[i]; j ++)
        {

            //if (j - ls > d)
              //  break;
      
            if (a[j] > a[i])
            {      
                //cout << i << " : " << j << endl;
                dp[j] = max(dp[j], dp[i] + 1);
            }
            else
            {
                if (j == n)
                    res = max(res, dp[i]);
                //ls = j;
            }
        }*/
    }

    //res = max(res, dp[n]);
    //assert(s <= res);
    cout << res << endl;
}
int main()
{
    solve();
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35