Submission #1145032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145032		erering	Global Warming (CEOI18_glo)	C++20	0 / 100	115 ms	17096 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define ll long long
#define int ll
const long long inf=1e18;
const int MOD=5000000;
const int N=2e5+5;
int seg[N*4],offset=1,last[N],last2[N];
void update(int idx,int val){
  idx+=offset;
  seg[idx]=val;
  idx/=2;
  while(idx>0){
    seg[idx]=max(seg[idx*2],seg[idx*2+1]);
    idx/=2;
  }
}
int query(int node,int qlo,int qhi,int lo,int hi){
  if(lo>=qlo && hi<=qhi){
    return seg[node];
  }
  if(lo>qhi || hi<qlo)return 0;
  int mid=(lo+hi)/2;
  return max(query(node*2,qlo,qhi,lo,mid),query(node*2+1,qlo,qhi,mid+1,hi));
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,d; cin>>n>>d;
  int a[n],b[n],cnt=1;
  map<int,int> mp;
  for(int i=0;i<n;i++){
    cin>>a[i];
    mp[a[i]];
    b[i]=a[i];
  }
  sort(b,b+n);
  int r=0;
  for(int i=0;i<n;i++){
    while(r<n && b[i]+d>b[r])r++;
    if(d!=0)last[b[i]]=(r<n?b[r-1]:-1);
    else last[b[i]]=(i==0?-2:last[b[i-1]]);
  }
  while(offset<mp.size()+d)offset*=2;
  offset*=2;
  for(auto i:mp){
    mp[i.first]=cnt++;
  }
  int pref[n],suff[n];
  for(int i=0;i<n;i++){
    if(last[a[i]]==-2)last2[mp[a[i]]]=-1;
    if(last[a[i]]==-1)last2[mp[a[i]]]=cnt;
    else last2[mp[a[i]]]=mp[last[a[i]]];
  }
  for(int i=0;i<n;i++){
    a[i]=mp[a[i]];
    int x=query(1,0,last2[a[i]],0,offset-1)+1;
    pref[i]=x;
    x=query(1,0,a[i]-1,0,offset-1)+1;
    update(a[i],x);
  }
  memset(seg,0,sizeof(seg));
  for(int i=n-1;i>=0;i--){
    int x=query(1,a[i],cnt-1,0,offset-1)+1;
    suff[i]=x;
    update(a[i],x);
  }
  int ans=suff[0];
  for(int i=1;i<n;i++){
    ans=max(ans,pref[i]+suff[i]-1);
  }
  cout<<ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25