oj.uz

Submission #395557

# Submission time Handle Problem Language Result Execution time Memory
395557 2021-04-28T13:56:45 Z Qw3rTy Global Warming (CEOI18_glo) C++11
15 / 100
 323 ms 78004 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(){
    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] = -INF; 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-1] + f[N+1-i]);
    }
    cout << res << '\n';
    return 0;
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:73:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   73 |     for(int i = 1; i <= N; ++i)cin >> a[i];  a[0] = -INF; a[N+1] = INF;
      |     ^~~
glo.cpp:73:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   73 |     for(int i = 1; i <= N; ++i)cin >> a[i];  a[0] = -INF; a[N+1] = INF;
      |                                              ^
glo.cpp:74:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   74 |     for(int i = 1; i <= N; ++i)b[i] = a[N+1-i]; b[0] = INF;
      |     ^~~
glo.cpp:74:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   74 |     for(int i = 1; i <= N; ++i)b[i] = a[N+1-i]; b[0] = INF;
      |                                                 ^
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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 75588 KB Output is correct
2 Correct 44 ms 75452 KB Output is correct
3 Correct 45 ms 75464 KB Output is correct
4 Correct 45 ms 75484 KB Output is correct
5 Correct 43 ms 75432 KB Output is correct
6 Correct 43 ms 75356 KB Output is correct
7 Correct 44 ms 75520 KB Output is correct
8 Correct 43 ms 75428 KB Output is correct
9 Correct 43 ms 75484 KB Output is correct
10 Correct 43 ms 75384 KB Output is correct
11 Correct 42 ms 75348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 75588 KB Output is correct
2 Correct 44 ms 75452 KB Output is correct
3 Correct 45 ms 75464 KB Output is correct
4 Correct 45 ms 75484 KB Output is correct
5 Correct 43 ms 75432 KB Output is correct
6 Correct 43 ms 75356 KB Output is correct
7 Correct 44 ms 75520 KB Output is correct
8 Correct 43 ms 75428 KB Output is correct
9 Correct 43 ms 75484 KB Output is correct
10 Correct 43 ms 75384 KB Output is correct
11 Correct 42 ms 75348 KB Output is correct
12 Correct 44 ms 75460 KB Output is correct
13 Correct 42 ms 75484 KB Output is correct
14 Correct 43 ms 75436 KB Output is correct
15 Correct 43 ms 75412 KB Output is correct
16 Correct 43 ms 75400 KB Output is correct
17 Correct 43 ms 75460 KB Output is correct
18 Correct 43 ms 75428 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 75588 KB Output is correct
2 Correct 44 ms 75452 KB Output is correct
3 Correct 45 ms 75464 KB Output is correct
4 Correct 45 ms 75484 KB Output is correct
5 Correct 43 ms 75432 KB Output is correct
6 Correct 43 ms 75356 KB Output is correct
7 Correct 44 ms 75520 KB Output is correct
8 Correct 43 ms 75428 KB Output is correct
9 Correct 43 ms 75484 KB Output is correct
10 Correct 43 ms 75384 KB Output is correct
11 Correct 42 ms 75348 KB Output is correct
12 Correct 44 ms 75460 KB Output is correct
13 Correct 42 ms 75484 KB Output is correct
14 Correct 43 ms 75436 KB Output is correct
15 Correct 43 ms 75412 KB Output is correct
16 Correct 43 ms 75400 KB Output is correct
17 Correct 43 ms 75460 KB Output is correct
18 Correct 43 ms 75428 KB Output is correct
19 Correct 45 ms 75496 KB Output is correct
20 Incorrect 45 ms 75484 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 1188 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 180 ms 76332 KB Output is correct
2 Correct 177 ms 76648 KB Output is correct
3 Correct 172 ms 76612 KB Output is correct
4 Incorrect 133 ms 76532 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 77012 KB Output is correct
2 Incorrect 320 ms 78004 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 75588 KB Output is correct
2 Correct 44 ms 75452 KB Output is correct
3 Correct 45 ms 75464 KB Output is correct
4 Correct 45 ms 75484 KB Output is correct
5 Correct 43 ms 75432 KB Output is correct
6 Correct 43 ms 75356 KB Output is correct
7 Correct 44 ms 75520 KB Output is correct
8 Correct 43 ms 75428 KB Output is correct
9 Correct 43 ms 75484 KB Output is correct
10 Correct 43 ms 75384 KB Output is correct
11 Correct 42 ms 75348 KB Output is correct
12 Correct 44 ms 75460 KB Output is correct
13 Correct 42 ms 75484 KB Output is correct
14 Correct 43 ms 75436 KB Output is correct
15 Correct 43 ms 75412 KB Output is correct
16 Correct 43 ms 75400 KB Output is correct
17 Correct 43 ms 75460 KB Output is correct
18 Correct 43 ms 75428 KB Output is correct
19 Correct 45 ms 75496 KB Output is correct
20 Incorrect 45 ms 75484 KB Output isn't correct
21 Halted 0 ms 0 KB -