oj.uz

Submission #395559

# Submission time Handle Problem Language Result Execution time Memory
395559 2021-04-28T14:02:15 Z Qw3rTy Global Warming (CEOI18_glo) C++11
0 / 100
 333 ms 76896 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 75448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 75448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 75448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 1228 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 76176 KB Output is correct
2 Correct 214 ms 76240 KB Output is correct
3 Correct 180 ms 76240 KB Output is correct
4 Incorrect 132 ms 76228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 333 ms 76896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 75448 KB Output isn't correct
2 Halted 0 ms 0 KB -