Submission #535840

#	Time	Username	Problem	Language	Result	Execution time	Memory
535840		shayanebrahimi	Financial Report (JOI21_financial)	C++14	100 / 100	575 ms	35612 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl                        '\n'
#define fast_io;                 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll MO=1e9+7;//998244353//1e9+9;
//ll tavmd(ll a,ll b){if(b==0){return 1;}if(b%2==0){ll x=tavmd(a,b/2);return(x*x)%MOd;}else{return(a%MOd*tavmd(a,b-1)%MOd)%MOd;}}
const ll MAXN=3e5+10;
const ll INF=8e18;
const ll LOG=30;
ll r[MAXN],a[MAXN],seg[4*MAXN],dp[MAXN];
vector<pair<ll,ll>>v;
set<ll>s;
void change(ll v,ll l,ll r,ll idx,ll x) {
      if(l==r){
            seg[v]=x;
            return;
      }
      ll mid=(l+r)/2;
      if(idx<=mid)
            change(2*v,l,mid,idx,x);
      else
            change(2*v+1,mid+1,r,idx,x);
      seg[v]=max(seg[2*v],seg[2*v+1]);
}
ll query(ll v,ll l,ll r,ll s,ll e){
      if(s<=l&&r<=e)
            return seg[v];
      ll res=0,mid=(l+r)/2;
      if(s<=mid)
            res=max(res,query(2*v,l,mid,s,e));
      if(e>mid)
            res=max(res,query(2*v+1,mid+1,r,s,e));
      return res;
}
int main(){
      fast_io;
      ll n,d;
      cin>>n>>d;
      for(int i=1;i<=n;i++){
            cin>>a[i];
            v.push_back({a[i],-i});
            if(i<=n-d+1)
                  s.insert(i);
      }
      sort(v.begin(),v.end());
      for(auto xx:v){
            ll idx=-xx.second;
            auto x=s.upper_bound(idx);
            r[idx]=min(n,(x==s.end()?n:*x+d-1));
            while(!s.empty()){
                  auto x=s.lower_bound(max(0ll,idx-d+1));
                  if(x==s.end()||*x>idx)
                        break;
                  s.erase(x);
            }
      }
      fill(seg,seg+4*MAXN,-INF);
      change(1ll,1ll,n,n,0ll);
      sort(v.rbegin(),v.rend());
      for(int i=0;i<n;i++) {
            ll idx=-v[i].second;
            dp[idx]=query(1ll,1ll,n,idx,r[idx])+1ll;
            change(1ll,1ll,n,idx,dp[idx]);
      }
      ll res=0;
      for(int i=1;i<=n;i++){
            res=max(res,dp[i]);
      }
      cout<<res;
      return 0;
}

Compilation message (stderr)

Main.cpp:5:9: warning: ISO C++11 requires whitespace after the macro name
    5 | #define fast_io;                 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
      |         ^~~~~~~

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