Submission #1228750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228750		vukhacminh	Global Warming (CEOI18_glo)	C++20	100 / 100	126 ms	11440 KiB

glo

/**
*    Author :  Vu Khac Minh
*    Created : 10.11.2024
**/
#include <bits/stdc++.h>
#define MASK(x) ((1ll) << (x))
#define BIT(x, i) (((x) >> (i)) & (1))
#define c_bit(i) __builtin_popcountll(i) 
#define SET_ON(x, i) ((x) | MASK(i)) 
#define SET_OFF(x, i) ((x) & ~MASK(i)) 
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = " << (val) << "] "
#define ll long long
#define int long long 
using namespace std;
const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;

int n, x;
int a[maxn], bit[maxn][2];

void file() {
    #define TASK "ROUNDPRI"
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
}

void update(int u, int val, int t)
{
    for(; u <= 2 * n; u += u & -u) bit[u][t] = max(bit[u][t], val);
    
}
int get(int u, int t) 
{
    int res = 0;
    for (; u; u -= u & -u) res = max(res, bit[u][t]);
    return res;
}

void solve() {
    vector<int> ctz;
    cin >> n >> x;
    FOR(i, 1, n)
    {
        cin >> a[i];
        ctz.push_back(a[i]);
        ctz.push_back(a[i] + x);
    }
    sort(ALL(ctz));
    ctz.erase(unique(ALL(ctz)), ctz.end());
    int res = 0;
    FOR(i, 1, n)
    {
        int val0 = lower_bound(ALL(ctz), a[i]) - ctz.begin() + 1;
        int val1 = lower_bound(ALL(ctz), a[i] + x) - ctz.begin() + 1;
        int len0 = 1 + get(val0 - 1, 0);
        int len1 = 1 + max(get(val1 - 1, 0), get(val1 - 1, 1));
        res = max({res, len0, len1});
        update(val0, len0, 0);
        update(val1, len1, 1);
    }
    cout << res;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    file();
    //cin >> ntest;
    while (ntest--)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'void file()':
glo.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25