Submission #395559

#	Time	Username	Problem	Language	Result	Execution time	Memory
395559		Qw3rTy	Global Warming (CEOI18_glo)	C++11	0 / 100	333 ms	76896 KiB

glo

#include <bits/stdc++.h>
#define INF 1e9+5
using namespace std;

const int maxN = 1e5+5;

int a[maxN];
int b[maxN];
int f[maxN]; //f[i] = longest decreasing subsequence of b that ends on N+1-i
int g[maxN]; //g[i] = longest increasing subsequence of a that ends on i
int N,d;

void testIO(){
    freopen("../test.in","r",stdin);
    return;
}

//Max Sparse Segment Tree

int tree[maxN<<6];
int lc[maxN<<6];
int rc[maxN<<6];
int cnt;

void init(){
    memset(tree,0,sizeof(tree));
    memset(lc,0,sizeof(lc));
    memset(rc,0,sizeof(rc));
    cnt = 1;
    tree[cnt] = lc[cnt] = rc[cnt] = 0;
    return;
}

int build(){
    assert(cnt <= (maxN<<6));
    tree[++cnt] = 0;
    lc[cnt] = 0;
    rc[cnt] = 0;
    return cnt;
}

void pushup(int p) {
    tree[p] = max(tree[lc[p]], tree[rc[p]]);
    return;
}

void update(int p, int l, int r, int a, int b, int val){
    if(a > r || b < l)return;
    if(a <= l && r <= b){
        tree[p] = val;
        return;
    }
    if(lc[p] == 0)lc[p] = build();
    if(rc[p] == 0)rc[p] = build();
    int mid = (l+r)>>1;
    update(lc[p],l,mid,a,b,val);
    update(rc[p],mid+1,r,a,b,val);
    pushup(p);
    return;
}

int query(int p, int l, int r, int a, int b){
    if(a > r || b < l)return 0;
    if(a <= l && r <= b)return tree[p];
    int mid = (l+r)>>1;
    return max(query(lc[p],l,mid,a,b),query(rc[p],mid+1,r,a,b));
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //testIO();
    cin >> N >> d;
    for(int i = 1; i <= N; ++i)cin >> a[i];
    a[0] = -1; a[N+1] = INF;
    for(int i = 1; i <= N; ++i)b[i] = a[N+1-i];
    b[0] = INF;
    init();
    for(int i = 1; i <= N; ++i){
        f[i] = max(f[i], query(1,0,INF,b[i]+1,INF) + 1);
        update(1,0,INF,b[i],b[i],f[i]);
    }
    init();
    for(int i = 1; i <= N; ++i){
        g[i] = max(g[i], query(1,0,INF,0,a[i]-1) + 1);
        update(1,0,INF,a[i],a[i],g[i]);
    }
    int res = 0;
    for(int i = 1; i <= N+1; ++i){
        if(a[i-1] - d < a[i])res = max(res, g[i] + f[N+1-i] - 1);
    }
    cout << res << '\n';
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'void testIO()':
glo.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   14 |     freopen("../test.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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