Submission #1165457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165457		enzy	Global Warming (CEOI18_glo)	C++20	100 / 100	426 ms	38592 KiB

glo

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+10;
int dp[maxn][2], seg[4*maxn][2], v[maxn], add[maxn];
map<int,int>relaciona;
void update(int t, int id, int ini, int fim, int cara, int val){
    if(ini==fim){
        seg[id][t]=max(seg[id][t],val);
        return;
    }
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    if(cara<=mid) update(t,e,ini,mid,cara,val);
    else update(t,d,mid+1,fim,cara,val);
    seg[id][t]=max(seg[e][t],seg[d][t]);
}
int query(int t, int id, int ini, int fim, int l, int r){
    if(r<l) return 0;
    if(ini>r||fim<l) return 0;
    if(ini>=l&&fim<=r) return seg[id][t];
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    return max(query(t,e,ini,mid,l,r),query(t,d,mid+1,fim,l,r));
}
signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, x; cin >> n >> x;
    set<int>comp;
    queue<int>q;
    for(int i=1;i<=n;i++){
        cin >> v[i];
        comp.insert(v[i]);
    }
    int cnt=1;
    for(int a : comp){
        relaciona[a]=cnt;
        q.push(a);
        while(!q.empty()){
            int u=q.front();
            if(u+x>a) break;
            q.pop();
            add[relaciona[u]]=relaciona[a]-relaciona[u];
        }
        cnt++;
    }
    while(!q.empty()){
        int u=q.front(); q.pop();
        add[relaciona[u]]=cnt-relaciona[u];
    }
    if(x==0) for(int i=1;i<=n;i++) add[i]=0;
    for(int i=1;i<=n;i++) v[i]=relaciona[v[i]];
    for(int i=1;i<=n;i++){ // vendo se o cara i for o ultimo cara da minha LIS
        dp[i][0]=query(0,1,1,n,1,v[i]-1)+1; // no estado zero eu ainda n usei o intervalo pra diminuir
        dp[i][1]=max(query(0,1,1,n,1,v[i]-1+add[v[i]]),query(1,1,1,n,1,v[i]-1))+1;
        update(0,1,1,n,v[i],dp[i][0]);
        update(1,1,1,n,v[i],dp[i][1]);
    }
    int resp=0;
    /*for(int i=1;i<=6;i++) cout << add[i] << " ";
    cout << endl;
    for(int i=1;i<=n;i++) cout << dp[i][0] << " ";
    cout << endl;
    for(int i=1;i<=n;i++) cout << dp[i][1] << " ";
    cout << endl;*/
    for(int i=1;i<=n;i++) resp=max({resp,dp[i][0],dp[i][1]});
    cout << resp << 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