Submission #723235

#	Time	Username	Problem	Language	Result	Execution time	Memory
723235		fdnfksd	Financial Report (JOI21_financial)	C++14	100 / 100	564 ms	39748 KiB

Main

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
set<int> s;
ll n,d,a[maxN];
vector<ll>v;
bool cmp(ll x,ll y)
{
    return a[x]<a[y];
}
ll lab[maxN],R[maxN],r[maxN];
ll findset(ll x)
{
    return lab[x]<0?x:lab[x]=findset(lab[x]);
}
void unite(ll u,ll v)
{
    u=findset(u);
    v=findset(v);
    if(u==v) return;
    if(lab[u]>lab[v]) swap(u,v);
    R[u]=max(R[u],R[v]);
    lab[u]+=lab[v];
    lab[v]=u;
}
ll dp[maxN],st[4*maxN];
void update(ll pos,ll val,ll id=1,ll l=1,ll r=n)
{
    if(l==r)
    {
        st[id]=max(st[id],val);
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) update(pos,val,id*2,l,mid);
    else update(pos,val,id*2+1,mid+1,r);
    st[id]=max(st[id*2],st[id*2+1]);
}
ll get(ll i,ll j,ll id=1,ll l=1,ll r=n)
{
    if(j<l||r<i) return 0;
    if(i<=l&&r<=j) return st[id];
    ll mid=l+r>>1;
    return max(get(i,j,id*2,l,mid),get(i,j,id*2+1,mid+1,r));
}
void solve()
{
    cin >> n >> d;
    for(int i=1;i<=n;i++) cin >> a[i],v.pb(i);
    sort(v.begin(),v.end(),cmp);
    ll j=0;
    for(int i=1;i<=n;i++) lab[i]=-1,R[i]=i;
    for(int i=0;i<v.size();i++)
    {
        while(j<v.size()&&a[v[j]]<=a[v[i]])
        {
            ll id=v[j];
            s.insert(id);
            auto it=s.upper_bound(id);
            if(it!=s.end())
            {
                if(abs(id-*it)<=d) unite(id,*it);
            }
            it=s.lower_bound(id);
            if(it!=s.begin())
            {
                it--;
                if(abs(id-*it)<=d) unite(*it,id);
            }
            j++;
        }
        r[v[i]]=min(n,R[findset(v[i])]+d);
    }
    j=v.size()-1;
    ll ans=0;
    for(int i=v.size()-1;i>=0;i--)
    {
        while(j>=0&&a[v[j]]>a[v[i]])
        {
            ll id=v[j];
            update(id,dp[id]);
            j--;
        }
        dp[v[i]]=get(v[i]+1,r[v[i]])+1;
        ans=max(ans,dp[v[i]]);
    }
    cout << ans;
    for(int i=1;i<=n;i++)
    {
        //cout << r[i]<<' ';
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void update(ll, ll, ll, ll, ll)':
Main.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     ll mid=l+r>>1;
      |            ~^~
Main.cpp: In function 'll get(ll, ll, ll, ll, ll)':
Main.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     ll mid=l+r>>1;
      |            ~^~
Main.cpp: In function 'void solve()':
Main.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
Main.cpp:64:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while(j<v.size()&&a[v[j]]<=a[v[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