oj.uz

Submission #482541

# Submission time Handle Problem Language Result Execution time Memory
482541 2021-10-25T13:26:35 Z Lam_lai_cuoc_doi Global Warming (CEOI18_glo) C++17
0 / 100
 108 ms 4992 KB 
#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

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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 4988 KB Output is correct
2 Correct 108 ms 4992 KB Output is correct
3 Correct 100 ms 4940 KB Output is correct
4 Correct 107 ms 4908 KB Output is correct
5 Incorrect 46 ms 4212 KB Output isn't correct

Subtask #5
0 / 20.0

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

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2668 KB Output is correct
2 Correct 41 ms 2664 KB Output is correct
3 Correct 86 ms 4992 KB Output is correct
4 Incorrect 46 ms 4212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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