oj.uz

Submission #1097088

# Submission time Handle Problem Language Result Execution time Memory
1097088 2024-10-06T03:35:58 Z Niosakaru Global Warming (CEOI18_glo) C++17
10 / 100
 47 ms 6980 KB 
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define N 200200

int n , x , p , fp , m , rt , l , r , mid , a[N] , b[N] , c[N] , d[N] , it[N << 2];
vector <int> vi;

void upd(int i,int l,int r,int p,int x){
    if (r < p || p < l) return;
    if (l == r) return it[i] = x, void();
    int mid = (l + r) >> 1;
    if (p <= mid) upd(i << 1,l,mid,p,x); else upd(i << 1|1,mid + 1,r,p,x);
    it[i] = max(it[i << 1] , it[i << 1|1]);  
}

int get(int i,int l,int r,int u,int v){
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return it[i];
    int mid = (l + r) >> 1;
    return max(get(i << 1,l,mid,u,v) , get(i << 1|1,mid + 1,r,u,v));
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> x;
    memset(d , 0x3f , sizeof d);
    for (int i = 1 ; i <= n ; i ++){
        cin >> a[i] , b[i] = lower_bound(d + 1,d + n + 1 , a[i]) - d; d[b[i]] = a[i];
        vi.push_back(a[i]) , vi.push_back(a[i] + x) , vi.push_back(a[i] - x);
        rt = max(rt,b[i]);
    } 
    memset(d , 0 , sizeof d);
    for (int i = n ; i ; i --){
        l = 1 , r = n;
        while (l <= r){
            mid = (l + r) >> 1;
            if (d[mid] <= a[i] - x) p = mid , r = mid - 1; else l = mid + 1;
        } 
        c[i] = p , rt = max(rt , c[i] + b[i] - 1);
        l = 1 , r = n;
        while (l <= r){
            mid = (l + r) >> 1;
            if (d[mid] <= a[i]) p = mid , r = mid - 1; else l = mid + 1;
        } 
        d[p] = a[i];
    }

    cout << rt << '\n';

    return 0;
}

/*

8 10
7 3 5 12 2 7 3 4

2
3
4
5
7
12
13
14
15
17
22

*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6864 KB Output is correct
2 Correct 43 ms 6860 KB Output is correct
3 Correct 45 ms 6868 KB Output is correct
4 Correct 47 ms 6980 KB Output is correct
5 Correct 35 ms 6864 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2780 KB Output is correct
2 Correct 11 ms 2752 KB Output is correct
3 Correct 10 ms 2776 KB Output is correct
4 Correct 9 ms 2780 KB Output is correct
5 Incorrect 1 ms 1196 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

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