oj.uz

Submission #422500

# Submission time Handle Problem Language Result Execution time Memory
422500 2021-06-10T07:34:56 Z Emin2004 Global Warming (CEOI18_glo) C++14
62 / 100
 105 ms 12740 KB 
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pii pair <ll, int>
#define pb push_back
#define F first
#define S second
#define ll long long
#define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define M_PI 3.14159265358979323846

const int N = 200005;
const int mod = 1e9 + 7;

ll lis[N], lds[N], a[N];
ll mp[N];

int main() {
    io;
    ll n, d;
    cin >> n >> d;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mp[i + 1] = INT_MAX;
    }
    ll ans = 0;
    mp[1] = a[0];
    lis[0] = 1;
    for(int i = 1; i < n; i++){
        ll l = 1, r = n;
        while(l <= r){
            ll mid = (l + r) / 2;
            if(mp[mid] < a[i]){
                mp[mid + 1] = min(mp[mid + 1], a[i]);
                lis[i] = max(lis[i], mid + 1);
                l = mid + 1;
                ans = max(ans, l);
            }
            else{
                r = mid - 1;
            }
        }
        mp[1] = min(mp[1], a[i]);
    }
    if(d == 0){
        cout << ans;
        return 0;
    }
    for(int i = 1; i <= n; i++){
        mp[i] = 0;
    }
    mp[1] = a[n - 1];
    lds[n - 1] = 1;
    for(int i = n - 2; i >= 0; i--){
        ll l = 1, r = n;
        while(l <= r){
            ll mid = (l + r) / 2;
            if(mp[mid] > a[i]){
                mp[mid + 1] = max(mp[mid + 1], a[i]);
                lds[i] = max(lds[i], mid + 1);
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        mp[1] = max(mp[1], a[i]);
    }
    for(int i = 1; i <= n; i++){
        mp[i] = -1;
    }
    set<pii> s;
    s.insert({a[0], 1});
    mp[1] = a[0];
    for(int i = 1; i < n; i++){
        ll cur = lds[i];
        ll k = a[i] + d;
        set<pii>::iterator itr = s.lower_bound({k, 0});
        if(itr != s.begin()) itr--;
        else continue;
        cur += (*itr).S;
        if(mp[lis[i]] > a[i]){
            s.erase(s.find({mp[lis[i]], lis[i]}));
            s.insert({a[i], lis[i]});
            mp[lis[i]] = a[i];
        }
        if(mp[lis[i]] == -1){
            s.insert({a[i], lis[i]});
            mp[lis[i]] = a[i];
        }
        ans = max(ans, cur);
    }
    cout << ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Incorrect 1 ms 332 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4952 KB Output is correct
2 Correct 53 ms 4872 KB Output is correct
3 Correct 43 ms 4880 KB Output is correct
4 Correct 46 ms 4952 KB Output is correct
5 Correct 36 ms 4880 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1908 KB Output is correct
2 Correct 32 ms 2396 KB Output is correct
3 Correct 19 ms 2396 KB Output is correct
4 Correct 21 ms 3740 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 31 ms 3680 KB Output is correct
7 Correct 17 ms 2240 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3424 KB Output is correct
2 Correct 48 ms 3468 KB Output is correct
3 Correct 105 ms 6512 KB Output is correct
4 Correct 91 ms 12740 KB Output is correct
5 Correct 62 ms 6596 KB Output is correct
6 Correct 97 ms 10652 KB Output is correct
7 Correct 79 ms 10692 KB Output is correct
8 Correct 38 ms 3236 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Incorrect 1 ms 332 KB Output isn't correct
21 Halted 0 ms 0 KB -