Submission #1081189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081189		abdelhakim	Financial Report (JOI21_financial)	C++14	0 / 100	351 ms	57332 KiB

Main

#include <bits/stdc++.h>
#define dbg(x) cout << #x <<' '<< x << endl; 
#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;
    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]];
    }
    ll l, r;
    l=r=0;
    deque<pair<ll,ll>> dq;
    for (int i = 0; i < d; i++)
    {
        while(!dq.empty() && dq.back().first >= order[i])
        {
            dq.pop_back();
        }
        dq.push_back({order[r], r});
        r++;
    }
    map<ll,ll> minsi;
    minsi[r-1] = dq[0].first;
    while(r<n)
    {
        while(!dq.empty() && dq.back().first >= order[r])
        {
            dq.pop_back();
        }
        dq.push_back({order[r], r});
        r++;
        if(l == dq[0].second) dq.pop_front();
        l++;
        minsi[r-1] = dq[0].first;
    }
    vector<ll> R(n);
    for (int i=n-1;i>=0;i--)
    {
        R[i] = query(1, n, order[i]+1, n, 0);
        if(R[i] == inf) R[i] = n-1;
        if(minsi[i] != 0)
        {
            update(1, n, minsi[i], i,0);
        }
    }
    vector<ll> dp(n,1);
    vector<pair<ll,ll>> v(n);
    for (int i=0;i<n;i++)
    {
        v[i] = {order[i],i};
    }
    sort(v.begin(), v.end(), [](pair<ll,ll> p1, pair<ll,ll> p2){if(p1.first == p2.first) return p1.second < p2.second; else return p1.first > p2.first;});
    for (int i = 0; i < n; i++)
    {
        dp[v[i].second] += query2(0,n-1,i,R[i],0);
        update2(0,n-1,v[i].second,dp[v[i].second],0);
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
}

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