Submission #1079625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079625		abdelhakim	Financial Report (JOI21_financial)	C++14	65 / 100	4008 ms	69200 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]);
}
vector<ll> tree2(maxn*4);
ll query2(ll l, ll r, ll x, ll y, ll node)
{
    if(max(l, x) > min(r, y))
    {
        return 0;
    }
    if(x <= l && r <= y)
    {
        return tree2[node];
    }
    ll mid = (l+r)/2;
    return max(query2(l, mid, x,y, node*2+1), query2(mid+1, r, x, y, node*2+2));
}
void update2(ll l, ll r, ll pos, ll val, ll node)
{
    if(pos > r || pos < l) return;
    if(l==r)
    {
        tree2[node] =  val;
        return;
    }
    ll mid  = (l+r)/2;
    update2(l, mid, pos, val, node*2+1);
    update2(mid+1, r, pos, val, node*2+2);
    tree2[node] = max(tree2[node*2+1], tree2[node*2+2]);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, d;
    cin >> n>> d;
    if(d == n)
    {
        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]];
        }
        vector<ll> dp(n,1);
        for (int i = n-1; i >= 0; i--)
        {
            dp[i] += query2(1, n, order[i] + 1, n, 0);
            update2(1, n, order[i], dp[i], 0);
        }
        cout << *max_element(dp.begin(),dp.end()) << endl;
    }
    else 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: 5 / 5
• Subtask 6: 0 / 35