Submission #123042

#	Time	Username	Problem	Language	Result	Execution time	Memory
123042		semiauto	Global Warming (CEOI18_glo)	C++14	100 / 100	656 ms	9156 KiB

glo

#include <bits/stdc++.h>
using namespace std;
int n,d,i,k,N=1,ans;
int mas[200001],num[200001],tree[530000],pdp[200001],sdp[200001];
pair <int,int> hey[200001];
int go(int x) {
    int i,pos=0;
    for (i=17;i>=0;i--) {
        if (pos+(1<<i)>n)
            continue;
        if (hey[pos+(1<<i)].first<x)
            pos+=(1<<i);
    }
    return num[hey[pos].second];
}
int gogo(int x) {
    int i,pos=0;
    for (i=17;i>=0;i--) {
        if (pos+(1<<i)>n)
            continue;
        if (hey[pos+(1<<i)].first<=x)
            pos+=(1<<i);
    }
    if (pos==n)
        return n+1;
    return num[hey[pos+1].second];
}
void update(int pos,int val) {
    pos+=N-1;
    while (pos) {
        tree[pos]=max(tree[pos],val);
        pos/=2;
    }
}
int solve(int p,int l,int r,int x,int y) {
    if (x>r || l>y)
        return 0;
    if (l>=x && r<=y)
        return tree[p];
    return max(solve(2*p,l,(l+r)/2,x,y),solve(2*p+1,(l+r)/2+1,r,x,y));
}
int main() {
    cin>>n>>d;
    while (N<n)
        N*=2;
    for (i=1;i<=n;i++) {
        cin>>mas[i];
        hey[i]={mas[i],i};
    }
    sort(hey+1,hey+n+1);
    for (i=1;i<=n;i++) {
        if (hey[i].first>hey[i-1].first)
            k++;
        num[hey[i].second]=k;
    }
    for (i=1;i<=n;i++) {
        pdp[i]=solve(1,N,2*N-1,N,N-1+num[i]-1)+1;
        update(num[i],pdp[i]);
    }
    for (i=1;i<530000;i++)
        tree[i]=0;
    for (i=n;i>0;i--) {
        sdp[i]=solve(1,N,2*N-1,N+num[i],2*N-1)+1;
        update(num[i],sdp[i]);
    }
    for (i=1;i<530000;i++)
        tree[i]=0;
    for (i=1;i<=n;i++) {
        ans=max(ans,solve(1,N,2*N-1,N,N-1+go(mas[i]+d))+sdp[i]);
        update(num[i],pdp[i]);
    }
     for (i=1;i<530000;i++)
        tree[i]=0;
    for (i=n;i>0;i--) {
        ans=max(ans,solve(1,N,2*N-1,N-1+gogo(mas[i]-d),2*N-1)+pdp[i]);
        update(num[i],sdp[i]);
    }
    cout<<ans<<endl;
  	return 0;
}

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