Submission #1129643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129643		alecurse	Global Warming (CEOI18_glo)	C++20	100 / 100	303 ms	7176 KiB

glo

#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
int reals=1;
vector<int> tree;

void add(int k, int x, int y, int l, int r, int val) {
    if(y<=l||x>=r) return;
    if(x>=l&&y<=r) {
        tree[k]=val;
        return;
    }
    int d = (x+y)/2;
    add(k*2,x,d,l,r,val);
    add(k*2+1,d,y,l,r,val);
    tree[k]=max(tree[k*2],tree[k*2+1]);
}

int getmax(int k, int x, int y, int l, int r) {
    if(y<=l||x>=r) return 0; 
    if(x>=l&&y<=r) {
        return tree[k];
    }
    int d = (x+y)/2;
    return max(getmax(k*2,x,d,l,r),getmax(k*2+1,d,y,l,r));
}
bool comp(pair<int,int> &a, pair<int,int> &b) {
    if(a.first==b.first) {
        return a.second>b.second;
    }
    return a.first<b.first;
}

int bsearch(int x, vector<pair<int,int> > &v, int N) {
    int a = 0, b=N-1;
    int minimo=N;
    while(a<=b) {
        int k = (a+b)/2;
        if(v[k].first>x) {
            minimo = min(minimo,k);
            b=k-1;
        } else {
            a=k+1;
        }
    }
    return minimo;
}
int main() {
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    int N,X;
    cin>>N>>X;
    // assert(X==0);
    vector<int> dp(N);
    vector<int> v(N);
    vector<pair<int,int> > vtosort(N);
    for(int i=0;i<N;i++) {
        cin>>v[i];
        vtosort[i].first=v[i];
        vtosort[i].second=i;
    }
    sort(vtosort.begin(),vtosort.end(),comp);
    vector<int> indexes(N);
    for(int i=0;i<N;i++) {
        indexes[vtosort[i].second]=i;
    }
    while(reals<=N)
        reals*=2;
    tree.resize(reals*2);
    for(int i=0;i<N;i++) {
        int maxbef = getmax(1,0,reals,0,indexes[i]);
        dp[i]=maxbef+1;
        add(1,0,reals,indexes[i],indexes[i]+1,dp[i]);
    }
    int maxres=0;
    for(int i=0;i<N;i++) {
        maxres=max(maxres,dp[i]);
    }
    tree.clear();
    tree.resize(reals*2);
    vector<int> newdp(N);
    for(int i=N-1;i>0;i--) {
        int maxbef = getmax(1,0,reals,indexes[i],reals);
        newdp[i]=maxbef+1;
        add(1,0,reals,indexes[i],indexes[i]+1,newdp[i]);
        int indextree = bsearch(v[i-1]-X,vtosort,N);
        // cout<<v[i-1]-X<<" "<<indextree<<"\n";
        int thsol = dp[i-1]+getmax(1,0,reals,indextree,reals);
        // cout<<indextree<<" "<<v[i-1]<<"\n";
        maxres=max(maxres,thsol);
    }
    cout<<maxres;

}

• 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