oj.uz

Submission #920235

# Submission time Handle Problem Language Result Execution time Memory
920235 2024-02-02T10:14:42 Z Mathii3u Global Warming (CEOI18_glo) C++14
62 / 100
 50 ms 13824 KB 
//#include <bits/myh.h>
#include<bits/stdc++.h>

// prime : M_19 5e6 , M_31 2e10
// __builtin_popcount , __builtin_ctz
// ./exec < input.txt 2> stderr.txt > stdout.txt 

using ull = unsigned long long;
using ll = long long;
using ld = long double;
using namespace std;
#define endl "\n";
#define F first
#define S second
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define pb push_back
#define BigInt __int128;
#define vi vector<int>
#define vpi vector<pi>
#define mi vector<vector<int>>
#define pi pair<int,int>
#define vll vector<ll>
#define mll vector<vll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define FOR(i, a, b) for (int i = a; i < b;i++)
#define FORS(i, a, b,step) for (int i = a; i < b;i += step)
#define sz(x) (int)x.size()
#define rev(v) reverse(v.begin(),v.end())
#define ITER(x,a) for(auto x : a )
#define sort_incr(a) sort(a.begin(),a.end())
#define sort_decr(a) sort(a.rbegin(),a.rend())
const ll MOD = 1e9 + 7;
int T;
int cases;

void print_state(mll & dp) {
    ITER(x,dp) {
        cout << x.back() << " ";
    }
    cout << endl;
}

void print_vll(vll & dp) {
    ITER(x,dp) {
        cout << x << " ";
    }
    cout << endl;
}

mll moves(vll t , vi & action) {
    rev(t);
    mll dp;
    FOR(i, 0, sz(t))
    {
        //print_state(dp);
        int id = sz(dp);
        int deb = 0;
        int fin = sz(dp);
        while(deb < fin) {
            int mid = (deb + fin) / 2;
            if (t[i] < dp[mid].back()) {
                deb = mid + 1;
            } else {
                id = mid;
                fin = mid;
            }
        }
        //cout << i << "-> " << id << endl;

        action[i] = id;
        if (id == sz(dp)) {
            dp.pb({t[i]});
        } else {
            dp[id].pb(t[i]);
        }
    }
    // print_state(dp);
    // cout << endl;
    return dp;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, x;
    cin >> n >> x;
    vll t(n);
    FOR(i, 0, n)
        cin >> t[i];

    vi action(n);
    mll dp_rev = moves(t, action);
    vll dp;
    ll best = sz(dp_rev);
    //print_state(dp_rev);
    FOR(i, 0, n - 1)
    {
        // maj [0;i]
        int id = lower_bound(dp.begin(), dp.end(), t[i]) - dp.begin();
        if (id == sz(dp)) {
            dp.pb(t[i]);
        } else {
            dp[id] = t[i];
        }

        // maj ]i;n-1]
        if (sz(dp_rev[action[n - 1 - i]]) == 1)
        {
            dp_rev.pop_back();
        } else {
            dp_rev[action[n - 1 - i]].pop_back();
        }

        ll sup_left = dp.back();
        ll deb = 0;
        ll fin = sz(dp_rev);
        while(deb < fin) {
            ll mid = (deb + fin) / 2;
            if (dp_rev[mid].back()+x > sup_left  ) {
                best = max(best, mid + 1 + sz(dp));
                deb = mid + 1;
            } else {
                fin = mid;
            }
        }

        ll sup_right = dp_rev.back().back();
        deb = 0;
        fin = sz(dp);
        while(deb < fin) {
            ll mid = (deb + fin) / 2;
            if (sup_right+x > dp[mid]  ) {
                best = max(best, mid + 1 + sz(dp_rev));
                deb = mid + 1;
            } else {
                fin = mid;
            }
        }
        //print_state(dp_rev);
    }
    //print_state(dp_rev);
    cout << best << endl;
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 600 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Incorrect 1 ms 348 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 47 ms 8800 KB Output is correct
2 Correct 49 ms 8612 KB Output is correct
3 Correct 50 ms 8784 KB Output is correct
4 Correct 48 ms 8704 KB Output is correct
5 Correct 39 ms 11008 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2400 KB Output is correct
2 Correct 11 ms 2392 KB Output is correct
3 Correct 11 ms 2392 KB Output is correct
4 Correct 9 ms 3092 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 10 ms 3088 KB Output is correct
7 Correct 10 ms 2392 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4440 KB Output is correct
2 Correct 23 ms 4432 KB Output is correct
3 Correct 47 ms 8784 KB Output is correct
4 Correct 39 ms 11780 KB Output is correct
5 Correct 20 ms 5644 KB Output is correct
6 Correct 30 ms 11976 KB Output is correct
7 Correct 38 ms 13824 KB Output is correct
8 Correct 19 ms 4308 KB Output is correct

Subtask #7
0 / 25.0

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