oj.uz

Submission #162072

# Submission time Handle Problem Language Result Execution time Memory
162072 2019-11-06T08:52:37 Z Akashi Global Warming (CEOI18_glo) C++14
48 / 100
 948 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;

int n, x;
int a[200005], s[200005];
int suf[200005], pref[200005];

int Sol = 0;

void find_lis(int d[], int st, int dr, int sgn){
    int L = 0;
    memset(s, 0, sizeof(s));

    for(int i = st; i != dr ; i += sgn){
        a[i] = a[i] * sgn;

        if(s[L] < a[i] || L == 0){
            s[++L] = a[i];
            d[i] = L;
        }
        else{
            int l = 1, dr = L;
            bool ok = true;
            while(l <= dr){
                int mij = (l + dr) / 2;

                if(s[mij] == a[i]){
                    ok = false;
                    d[i] = mij;
                    break ;
                }

                if(s[mij] > a[i]) dr = mij - 1;
                else l = mij + 1;
            }

            if(s[dr] == a[i]){
                ok = false;
                d[i] = dr;
            }

            if(!ok) continue ;

            s[l] = a[i], d[i] = l;
        }
    }

    Sol = max(Sol, L);

    for(int i = 1; i <= n ; ++i) a[i] = a[i] * sgn;
}

struct node{
    int val;
    node *left, *right;

    node(){
        val = 0;
        left = right = 0;
    }
};

node *arb;

int query(int x, int y, int st = 1, int dr = 1e9, node *nod = arb){
    if(nod == NULL) return 0;
    if(x <= st && dr <= y) return nod->val;

    int mij = (st + dr) / 2;
    int a1 = 0, a2 = 0;
    if(x <= mij) a1 = query(x, y, st, mij, nod->left);
    if(mij + 1 <= y) a2 = query(x, y, mij + 1, dr, nod->right);

    return max(a1, a2);
}

void update(int val, int pos, int st = 1, int dr = 1e9, node *nod = arb){
    if(st == dr){
        nod->val = val;
        return ;
    }

    if(nod->left == NULL) nod->left = new node;
    if(nod->right == NULL) nod->right = new node;

    int mij = (st + dr) / 2;
    if(pos <= mij){
        update(val, pos, st, mij, nod->left);
    }
    else{
        update(val, pos, mij + 1, dr, nod->right);
    }

    nod->val = max(nod->left->val, nod->right->val);
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d%d", &n, &x);

    for(int i = 1; i <= n ; ++i) scanf("%d", &a[i]);

    find_lis(pref, 1, n + 1, 1);
    find_lis(suf, n, 0, -1);

    arb = new node;
    update(pref[1], a[1]);
    for(int i = 1; i < n ; ++i){
        int aux = suf[i + 1];
        aux = aux + query(max(a[i + 1] - x + 1, 1), min(a[i + 1] + x - 1, 1000000000));
        Sol = max(Sol, aux);

        update(pref[i + 1], a[i + 1]);
    }

    arb = new node;
    update(suf[n], a[n]);
    for(int i = n; i > 1 ; --i){
        int aux = pref[i - 1];
        aux = aux + query(max(a[i - 1] - x + 1, 1), min(a[i - 1] + x - 1, 1000000000));
        Sol = max(Sol, aux);

        update(suf[i - 1], a[i - 1]);
    }

    printf("%d", Sol);

    return 0;
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &x);
     ~~~~~^~~~~~~~~~~~~~~~
glo.cpp:103:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n ; ++i) scanf("%d", &a[i]);
                                  ~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1116 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1148 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct
11 Correct 3 ms 1144 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1116 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1148 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct
11 Correct 3 ms 1144 KB Output is correct
12 Correct 3 ms 1144 KB Output is correct
13 Correct 3 ms 1144 KB Output is correct
14 Correct 3 ms 1144 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 3 ms 1144 KB Output is correct
17 Correct 3 ms 1272 KB Output is correct
18 Correct 3 ms 1144 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1116 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1148 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct
11 Correct 3 ms 1144 KB Output is correct
12 Correct 3 ms 1144 KB Output is correct
13 Correct 3 ms 1144 KB Output is correct
14 Correct 3 ms 1144 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 3 ms 1144 KB Output is correct
17 Correct 3 ms 1272 KB Output is correct
18 Correct 3 ms 1144 KB Output is correct
19 Correct 9 ms 3704 KB Output is correct
20 Correct 9 ms 3704 KB Output is correct
21 Correct 9 ms 3704 KB Output is correct
22 Correct 9 ms 3708 KB Output is correct
23 Correct 7 ms 2424 KB Output is correct
24 Correct 7 ms 2396 KB Output is correct
25 Correct 4 ms 1272 KB Output is correct
26 Correct 5 ms 1272 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 948 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 92528 KB Output is correct
2 Correct 275 ms 92344 KB Output is correct
3 Correct 282 ms 92452 KB Output is correct
4 Correct 142 ms 50168 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 89 ms 8208 KB Output is correct
7 Correct 194 ms 64508 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 171284 KB Output is correct
2 Correct 529 ms 171136 KB Output is correct
3 Runtime error 858 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1116 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1148 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct
11 Correct 3 ms 1144 KB Output is correct
12 Correct 3 ms 1144 KB Output is correct
13 Correct 3 ms 1144 KB Output is correct
14 Correct 3 ms 1144 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 3 ms 1144 KB Output is correct
17 Correct 3 ms 1272 KB Output is correct
18 Correct 3 ms 1144 KB Output is correct
19 Correct 9 ms 3704 KB Output is correct
20 Correct 9 ms 3704 KB Output is correct
21 Correct 9 ms 3704 KB Output is correct
22 Correct 9 ms 3708 KB Output is correct
23 Correct 7 ms 2424 KB Output is correct
24 Correct 7 ms 2396 KB Output is correct
25 Correct 4 ms 1272 KB Output is correct
26 Correct 5 ms 1272 KB Output is correct
27 Runtime error 948 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Halted 0 ms 0 KB -