Submission #482541

#	Time	Username	Problem	Language	Result	Execution time	Memory
482541		Lam_lai_cuoc_doi	Global Warming (CEOI18_glo)	C++17	0 / 100	108 ms	4992 KiB

glo

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 2e5 + 5;
// Obvious: We only increase/decrease prefix or suffix

struct FenwickTree
{
    int n, a[N];
    void Update(int p, int v)
    {
        if (p == 0)
            return;
        for (; p <= n; p += p & -p)
            a[p] = max(a[p], v);
    }
    int Get(int p)
    {
        int ans(0);
        for (; p > 0; p -= p & -p)
            ans = max(ans, a[p]);
        return ans;
    }
} f, g;

int n, m;
ll a[N], x, b[N];

void Read()
{
    cin >> n >> x;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        b[i] = a[i];
    }
}

void Solve()
{
    sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - b - 1;
    f.n = g.n = m;

#define Find(x, v) (lower_bound(x + 1, x + m + 1, v) - x)

    for (int i = 1; i <= n; ++i)
    {
        int u = Find(b, a[i]) - 1,
            v = Find(b, a[i] + x) - 1;

        int p = f.Get(u),
            q = f.Get(v),
            r = g.Get(u);

        f.Update(u, p + 1);
        g.Update(u, max(q, r) + 1);
    }

    cout << g.Get(m);
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("xor.INP", "r"))
    {
        freopen("xor.inp", "r", stdin);
        freopen("xor.out", "w", stdout);
    }
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case #" << _ << ": ";
        Read();
        Solve();
    }
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message (stderr)

glo.cpp: In function 'void read(T&)':
glo.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^
glo.cpp: In function 'int32_t main()':
glo.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen("xor.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen("xor.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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