Submission #1094951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094951		HiepVu217	Global Warming (CEOI18_glo)	C++17	100 / 100	288 ms	7732 KiB

glo

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 17;
int n, c, a[N], b[N], ans;
int st[4 * N], fl[N], fr[N];
void build (int id, int l, int r)
{
    st[id] = 0;
    if (l == r)
    {
        return;
    }
    int mid = l + r >> 1;
    build (id * 2, l, mid);
    build (id * 2 + 1, mid + 1, r);
}
void update (int id, int l, int r, int u, long long z)
{
    if (l == r)
    {
        st[id] = z;
        return;
    }
    int mid = l + r >> 1;
    if (u <= mid)
    {
        update (id * 2, l, mid, u, z);
    }
    else
    {
        update (id * 2 + 1, mid + 1, r, u, z);
    }
    st[id] = max (st[id * 2], st[id * 2 + 1]);
}
int get (int id, int l, int r, int u, int v)
{
    if (u > r || l > v)
    {
        return 0;
    }
    if (u <= l && v >= r)
    {
        return st[id];
    }
    int mid = l + r >> 1;
    return max (get (id * 2, l, mid, u, v), get (id * 2 + 1, mid + 1, r, u, v));
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> c;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sort (b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        int id = lower_bound (b + 1, b + n + 1, a[i]) - b;
        fr[i] = get (1, 1, n, 1, id - 1) + 1;
        update (1, 1, n, id, fr[i]);
    }
    build (1, 1, n);
    for (int i = n; i >= 1; --i)
    {
        int id = lower_bound (b + 1, b + n + 1, a[i]) - b;
        fl[i] = get (1, 1, n, 1, n - id) + 1;
        update (1, 1, n, n - id + 1, fl[i]);
    }
    build (1, 1, n);
    for (int i = 1; i <= n; ++i)
    {
        int id = lower_bound (b + 1, b + n + 1, a[i] + c) - b;
        ans = max (ans, get (1, 1, n, 1, id - 1) + fl[i]);
        id = lower_bound (b + 1, b + n + 1, a[i]) - b;
        update (1, 1, n, id, fr[i]);
    }
    cout << ans;
}

Compilation message (stderr)

glo.cpp: In function 'void build(int, int, int)':
glo.cpp:13:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |     int mid = l + r >> 1;
      |               ~~^~~
glo.cpp: In function 'void update(int, int, int, int, long long int)':
glo.cpp:24:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |     int mid = l + r >> 1;
      |               ~~^~~
glo.cpp: In function 'int get(int, int, int, int, int)':
glo.cpp:45:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int mid = l + r >> 1;
      |               ~~^~~

• 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