Submission #930576

#	Time	Username	Problem	Language	Result	Execution time	Memory
930576		aykhn	Global Warming (CEOI18_glo)	C++17	100 / 100	189 ms	15032 KiB

glo

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct BIT
{
    int n;
    vector<int> ft;
    void init(int N)
    {
        n = N + 5;
        ft.assign(n + 5, 0);
    }
    void make(int pos, int val)
    {
        for (pos = pos + 1; pos <= n; pos += pos & -pos) ft[pos] = max(ft[pos], val);
    }
    int get(int pos, int res = 0)
    {
        for (pos = pos + 1; pos > 0; pos -= pos & -pos) res = max(res, ft[pos]);
        return res;
    }
};

vector<int> mp;

int id(int x)
{
    return lower_bound(mp.begin(), mp.end(), x) - mp.begin();
}

signed main()
{
    int n, d;
    cin >> n >> d;
    int a[n], b[n];
    for (int &i : a)
    {
        cin >> i;
        mp.push_back(i), mp.push_back(i + d);
    }
    sort(mp.begin(), mp.end());
    mp.resize(unique(mp.begin(), mp.end()) - mp.begin());
    BIT ft1, ft2;
    ft1.init(2*n), ft2.init(2*n);
    for (int i = 0; i < n; i++)
    {
        b[i] = id(a[i] + d);
        a[i] = id(a[i]);
        int x = ft1.get(a[i] - 1), y = ft1.get(b[i] - 1), z = ft2.get(b[i] - 1);
        ft1.make(a[i], x + 1);
        ft2.make(b[i], max(y, z) + 1);
    }
    cout << max(ft1.get(2 * n), ft2.get(2 * n)) << '\n';
}

• 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