Submission #427459

#	Time	Username	Problem	Language	Result	Execution time	Memory
427459		DanerZein	Financial Report (JOI21_financial)	C++14	40 / 100	4066 ms	81668 KiB

Main

#include <bits/stdc++.h>
#define index int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int MAX_P=3e5*4;
int n,d;
vector<int> x;
map<ii,int> dp;
int finan(int id,int ma){
  if(dp.find(ii(id,ma))!=dp.end()) return dp[ii(id,ma)];
  if(id==n-1) return 0;
  int ans=0;
  for(int i=id+1;i<n && i<=id+d;i++){
    ans=max(ans,finan(i,max(ma,x[i]))+(x[i]>ma));
  }
  return dp[ii(id,ma)]=ans;
}
int tr[MAX_P],la[MAX_P];
void init(int node,int a,int b){
  if(a==b){
    tr[node]=0;
    la[node]=-1;
    return;
  }
  index;
  init(le,a,mid);
  init(ri,mid+1,b);
  tr[node]=0; la[node]=-1;
}
void propagar(int node,int a,int b){
  if(la[node]==-1) return;
  tr[node]=la[node];
  int val=la[node];
  la[node]=-1;
  if(a==b) return;
  index;
  la[le]=val;
  la[ri]=val;
}
void update(int node,int a,int b,int l,int r,int val){
  propagar(node,a,b);
  if(b<l || a>r) return;
  if(l<=a && r>=b){
    la[node]=val;
    propagar(node,a,b);
    return;
  }
  index;
  update(le,a,mid,l,r,val);
  update(ri,mid+1,b,l,r,val);
  tr[node]=tr[le]+tr[ri];
}
int main(){
  scanf("%d%d",&n,&d);
  for(int i=0;i<n;i++){
    int a; scanf("%d",&a);
    x.push_back(a);
  }
  int ans=0;
  if(d!=1){
    for(int i=0;i<n;i++){
      ans=max(ans,finan(i,x[i])+1);
    }
    printf("%d\n",ans);
  }
  else{
    init(0,0,n-1);
    map<int,int> ids;
    set<int> se;
    for(int i=0;i<n;i++) se.insert(x[i]);
    int c=0;
    for(auto &v:se){
      ids[v]=c;
      c++;
    }
    int ans=0;
    for(int i=n-1;i>=0;i--){
      update(0,0,n-1,0,ids[x[i]],0);
      update(0,0,n-1,ids[x[i]],ids[x[i]],1);
      ans=max(ans,tr[0]);
    }
    cout<<ans<<endl;
  }
}

Compilation message (stderr)

Main.cpp: In function 'void propagar(int, int, int)':
Main.cpp:2:19: warning: unused variable 'mid' [-Wunused-variable]
    2 | #define index int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
      |                   ^~~
Main.cpp:37:3: note: in expansion of macro 'index'
   37 |   index;
      |   ^~~~~
Main.cpp: In function 'int main()':
Main.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d",&n,&d);
      |   ~~~~~^~~~~~~~~~~~~~
Main.cpp:57:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     int a; scanf("%d",&a);
      |            ~~~~~^~~~~~~~~

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