Submission #1066870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066870		Namviet2704	Global Warming (CEOI18_glo)	C++17	100 / 100	805 ms	159680 KiB

glo

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 2;

int n, x, a[N];
int nNode;
int ver[N];

struct node
{
    int left, right;
    int ln;
    node () {}
    node(int ln, int left, int right) : ln(ln), left(left), right(right) {}
} it[20000000], it1[20000000];

inline void refine(int cur) {
    it[cur].ln = max(it[it[cur].left].ln, it[it[cur].right].ln);
}

int update(int oldId, int l, int r, int u, int val)
{
    if(l == r)
    {
        ++nNode;
        it[nNode] = node(max(it[oldId].ln, val), 0, 0);
        return nNode;
    }
    int mid = (l + r) >> 1;
    int cur = ++nNode;

    if(u <= mid)
    {
        it[cur].left = update(it[oldId].left, l, mid, u, val);
        it[cur].right = it[oldId].right;
    }
    else
    {
        it[cur].right = update(it[oldId].right, mid + 1, r, u, val);
        it[cur].left = it[oldId].left;
    }
    refine(cur);
    return cur;
}

int get(int nodeId, int l, int r, int u, int v)
{
    if (v < l || r < u)
        return -1;
    if (u <= l && r <= v)
        return it[nodeId].ln;

    int mid = (l + r) >> 1;
    return max(get(it[nodeId].left, l, mid, u, v),
               get(it[nodeId].right, mid + 1, r, u, v));
}

inline void refine1(int cur) {
    it1[cur].ln = max(it1[it1[cur].left].ln, it1[it1[cur].right].ln);
}

int update1(int oldId, int l, int r, int u, int val)
{
    if(l == r)
    {
        ++nNode;
        it1[nNode] = node(max(it1[oldId].ln, val), 0, 0);
        return nNode;
    }
    int mid = (l + r) >> 1;
    int cur = ++nNode;

    if(u <= mid)
    {
        it1[cur].left = update(it1[oldId].left, l, mid, u, val);
        it1[cur].right = it1[oldId].right;
    }
    else
    {
        it1[cur].right = update(it1[oldId].right, mid + 1, r, u, val);
        it1[cur].left = it1[oldId].left;
    }
    refine1(cur);
    return cur;
}

int get1(int nodeId, int l, int r, int u, int v)
{
    if (v < l || r < u)
        return -1;
    if (u <= l && r <= v)
        return it1[nodeId].ln;

    int mid = (l + r) >> 1;
    return max(get(it1[nodeId].left, l, mid, u, v),
               get(it1[nodeId].right, mid + 1, r, u, v));
}

int st[12 * N];

void build(int id, int l, int r)
{
    if(l == r)
    {
        st[id] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = 0;
}

void upd(int id, int l, int r, int u, int v)
{
    if(l == r)
    {
        st[id] = max(st[id], v);
        return;
    }
    int mid = (l + r) >> 1;
    if(u <= mid)
        upd(id * 2, l, mid, u, v);
    else
        upd(id * 2 + 1, mid + 1, r, u, v);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}

int gett(int nodeId, int l, int r, int u, int v)
{
    if (v < l || r < u)
        return -1;
    if (u <= l && r <= v)
        return st[nodeId];

    int mid = (l + r) >> 1;
    return max(gett(nodeId * 2, l, mid, u, v),
               gett(nodeId * 2 + 1, mid + 1, r, u, v));
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> x;
    vector<int> nen;
    nen.push_back(-1e9);
    nen.push_back(1e9);
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        nen.push_back(a[i]);
        nen.push_back(a[i] + x);
        nen.push_back(a[i] - x);
    }
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());
    int m = nen.size();
    for(int i = n; i >= 1; i--)
    {
        int l = upper_bound(nen.begin(), nen.end(), a[i]) - nen.begin();
        int tmp = get(ver[i + 1], 1, m, l + 1, m);
//        cout << tmp << '\n';
        ver[i] = update(ver[i + 1], 1, m, l, tmp + 1);
//        cout << i << " " << l << " " << tmp + 1 << '\n';
    }
    int ans = it[ver[1]].ln;
    for(int i = 1; i <= n; i++)
    {
        int r = upper_bound(nen.begin(), nen.end(), a[i]) - nen.begin(), l = upper_bound(nen.begin(), nen.end(), a[i] - x) - nen.begin();
        int tmp = gett(1, 1, m, 1, r - 1);
//        cout << tmp << " " << get(ver[i + 1], 1, m, l + 1, m) << " " << l << " " << m << "huhu\n";
        ans = max(ans, tmp + 1 + get(ver[i + 1], 1, m, l + 1, m));
        upd(1, 1, m, r, tmp + 1);
    }
    build(1, 1, m);
    memset(ver, 0, sizeof ver);
    for(int i = 1; i <= n; i++)
    {
        int l = upper_bound(nen.begin(), nen.end(), a[i]) - nen.begin();
        int tmp = get1(ver[i - 1], 1, m, 1, l - 1);
//        cout << tmp << '\n';
        ver[i] = update1(ver[i - 1], 1, m, l, tmp + 1);
//        cout << i << " " << l << " " << tmp + 1 << '\n';
    }
    for(int i = n; i >= 1; i--)
    {
        int l = upper_bound(nen.begin(), nen.end(), a[i]) - nen.begin(), r = upper_bound(nen.begin(), nen.end(), a[i] + x) - nen.begin();
        int tmp = gett(1, 1, m, l + 1, m);
//        cout << tmp << " " << get(ver[i + 1], 1, m, l + 1, m) << " " << l << " " << m << "huhu\n";
        ans = max(ans, tmp + 1 + get1(ver[i - 1], 1, m, 1, r - 1));
        upd(1, 1, m, l, tmp + 1);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

glo.cpp: In constructor 'node::node(int, int, int)':
glo.cpp:14:9: warning: 'node::ln' will be initialized after [-Wreorder]
   14 |     int ln;
      |         ^~
glo.cpp:13:9: warning:   'int node::left' [-Wreorder]
   13 |     int left, right;
      |         ^~~~
glo.cpp:16:5: warning:   when initialized here [-Wreorder]
   16 |     node(int ln, int left, int right) : ln(ln), left(left), right(right) {}
      |     ^~~~

• 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