Submission #1078096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078096		abdelhakim	Financial Report (JOI21_financial)	C++14	60 / 100	4021 ms	59684 KiB

Main

#include <bits/stdc++.h>
#define mod 1000000007LL
#define inf 1e17
#define ll long long
using namespace std;

void printvec(vector<ll> vec) {
    for (auto &&e : vec) {
        cout << e << ' ';
    }
    cout << endl;
}
ll maxn = 300000+5;
vector<ll> tree(4*maxn, inf);
ll query(ll l, ll r, ll x, ll y, ll node)
{
    if(max(l, x) > min(r, y))
    {
        return inf;
    }
    if(x <= l && r <= y)
    {
        return tree[node];
    }
    ll mid = (l+r)/2;
    return min(query(l, mid, x,y, node*2+1), query(mid+1, r, x, y, node*2+2));
}
void update(ll l, ll r, ll pos, ll val, ll node)
{
    if(pos > r || pos < l) return;
    if(l==r)
    {
        tree[node] =  val;
        return;
    }
    ll mid  = (l+r)/2;
    update(l, mid, pos, val, node*2+1);
    update(mid+1, r, pos, val, node*2+2);
    tree[node] = min(tree[node*2+1], tree[node*2+2]);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, d;
    cin >> n>> d;
    if(d==1)
    {
        vector<ll> a(n);
        for(int i=0; i < n; i++) cin >> a[i];
        vector<ll> temp = a;
        sort(temp.begin(),temp.end());
        vector<ll> order(n);
        map<ll,ll> rnk;
        ll cur=0;
        for (int i = 0; i < n;i++)
        {
            if(i == 0 || temp[i]!=temp[i-1])
            {
                cur++;
            }
            rnk[temp[i]] = cur;
        }
        for (int i = 0; i < n; i++)
        {
            order[i] = rnk[a[i]];
        }
        map<ll,ll> nxtmx;
        for (int i = n-1; i >= 0; i--)
        {
            ll nxt = query(1, n, order[i]+1,n,0);
            if(nxt == inf) nxtmx[i]=-1;
            else nxtmx[i] = nxt;
            update(1, n, order[i], i,0);
        }
        vector<ll> dp(n,1);
        dp.back() = 1;
        for (int i = n-2; i >= 0; i--)
        {
            if(nxtmx[i]!=-1) dp[i]+=dp[nxtmx[i]];
        }
        cout << *max_element(dp.begin(), dp.end()) << endl;
    }
    else{
    vector<ll> a(n);
    for(int i=0; i < n; i++) cin >> a[i];
    vector<ll> dp(n,1);
    dp.back() = 1;
    for (int i  = n-2; i >= 0; i--)
    {
        ll cur = 0;
        for (int j=i+1; j < n; j++)
        {
            if(a[j] > a[i])
            {
                cur++;
                dp[i] = max(dp[i], 1 + dp[j]);
                if(cur == d)break;
            }
            else cur = 0;
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
    }
}

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