Submission #1279298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279298		avohado	Global Warming (CEOI18_glo)	C++20	30 / 100	382 ms	75424 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
#define mp make_pair
#define all(x) x.begin(), x.end()
struct Node{
    int l=-1, r=-1, val=0;
};
Node ex;
vector<Node>tree[2];
int inf=1e9+1, sh[2]={1,1};
void upd(int v, int j, int l, int tl, int tr, int val){
    tree[j][v].val=max(tree[j][v].val, val);
    if(tl==tr){
        return;
    }
    int tm=(tl+tr)/2;
    if(tr-tm<tm-tl){
        tm--;
    }
    if(tm<l){
        if(tree[j][v].r==-1){
            tree[j][v].r=sh[j];sh[j]++;
            tree[j].pb(ex);
        }
        upd(tree[j][v].r, j,l, tm+1, tr, val);
    }else{
        if(tree[j][v].l==-1){
            tree[j][v].l=sh[j];sh[j]++;
            tree[j].pb(ex);
        }
        upd(tree[j][v].l, j,l, tl, tm, val);
    }
}
int get(int v, int j, int l, int r, int tl, int tr){
    if(l<=tl&&tr<=r){
        return tree[j][v].val;
    }
    if(l>tr||tl>r){
        return 0;
    }
    int tm=(tl+tr)/2;
    if(tree[j][v].l==-1)
    return get(tree[j][v].r, j, l, r, tm+1, tr);
    if(tree[j][v].r==-1)
    return get(tree[j][v].l, j, l, r, tl, tm);
    return max(get(tree[j][v].l, j, l, r, tl, tm), get(tree[j][v].r, j, l, r, tm+1, tr));
}
void solve(){
    int n, m;
    cin >> n >> m;
    int a[n];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    tree[0].pb(ex);
    tree[1].pb(ex);
    upd(0, 0, inf, -inf, inf, 0);
    upd(0, 0, inf, -inf, inf, 0);
    for(int i=n-1; i>=0; i--){
        int f=max(get(0, 0,a[i]+1-m, inf, -inf, inf),get(0, 1,a[i]+1-m, inf, -inf, inf));
        upd(0, 1, a[i]-m, -inf, inf, f+1);
        f=get(0, 0,a[i]+1, inf, -inf, inf);
        upd(0, 0, a[i], -inf, inf, f+1);
    }
    cout << tree[1][0].val;
}
int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int t=1;
    //cin >> t;
    while(t--){
        solve();
        cout << "\n";
    }
    return 0;
}

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