Submission #420014

#	Time	Username	Problem	Language	Result	Execution time	Memory
420014		Runtime_error_	Financial Report (JOI21_financial)	C++14	100 / 100	885 ms	37416 KiB

Main

//JOIOC 2021 p2 finanicial
#include <bits/stdc++.h>
#define le node+node
#define ri node+node+1
#define mid (l+r)/2
#define pi pair<int,int>
using namespace std;
const int inf = 3e5+9;
int n,d,ans,cnt,a[inf],dp[inf];
map<int,int> mp;

int tree[inf<<2];
void update(int node,int l,int r,int idx,int val,int del){
    if(l == r){
        if(del)
            return void(tree[node] = val);
        return void(tree[node] = max(tree[node],val));
    }
    if(idx<=mid)
        update(le,l,mid,idx,val,del);
    else
        update(ri,mid+1,r,idx,val,del);
    tree[node] = max(tree[le],tree[ri]);
}

int query(int node,int l,int r,int x,int y){
    if(l>r || r<x || l>y || x>y)
        return 0;
    if(l>=x && r<=y)
        return tree[node];
    return max(query(le,l,mid,x,y),query(ri,mid+1,r,x,y));
}
deque<pair<int,int> > dq;//pair<time,val>
set<int> vals;

int main(){
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i),mp[a[i]];

    for(auto &o:mp)
        o.second = ++cnt;
    for(int i=1;i<=n;i++)
        a[i] = mp[a[i]];

    for(int i=1;i<=n;i++){
        dp[i] = query(1,1,cnt,1,a[i]-1)+1;
        update(1,1,cnt,a[i],dp[i],0);
        vals.insert(a[i]);
        if(i == n)
            ans = tree[1];
        //cout<<dp[i]<<" ";
        while(!dq.empty() && dq.back().second >= a[i])
            dq.pop_back();
        dq.push_back(pi(i,a[i]));
        while(dq.front().first <= i-d)
            dq.pop_front();
        int LimitToDelete = dq.front().second-1;
        while(!vals.empty() && *vals.begin() <= LimitToDelete){
            update(1,1,cnt,*vals.begin(),0,1);
            vals.erase(vals.begin());
        }
    }
    printf("%d\n",ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d%d",&n,&d);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%d",a+i),mp[a[i]];
      |         ~~~~~^~~~~~~~~~

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