Submission #880950

#	Time	Username	Problem	Language	Result	Execution time	Memory
880950		cpptowin	Global Warming (CEOI18_glo)	C++17	100 / 100	200 ms	26244 KiB

glo

#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 400010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf 1000000000
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1 << j))
#define onbit(i, j) (i | (1 << j))
#define vi vector<int>
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
struct BIT
{
    int t[maxn];
    void up(int x, int val)
    {
        for (; x; x -= lb(x))
            t[x] = max(t[x], val);
    }
    int get(int x)
    {
        int ans = 0;
        for (; x < maxn; x += lb(x))
            ans = max(ans, t[x]);
        return ans;
    }
} t2;
struct BIT1
{
    int t[maxn];
    void up(int x, int val)
    {
        for (; x < maxn; x += lb(x))
            t[x] = max(val, t[x]);
    }
    int get(int x)
    {
        int ans = 0;
        for (; x; x -= lb(x))
            ans = max(ans, t[x]);
        return ans;
    }
} t1;
int LIS(int arr[], int n)
{
    fo(i, 0, n) t1.t[i] = 0;
    vi v;
    fo(i, 1, n) v.pb(arr[i]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int now = 0;
    fo(i, 1, n)
    {
        int lb = lower_bound(v.begin(), v.end(), arr[i]) - v.begin() + 1;
        int val = t1.get(lb) + 1;
        now = max(now, val);
        t1.up(lb + 1, val);
    }
    return now;
}
int n, x;
int a[maxn];
namespace sub2
{
    int arr[maxn];
    void solve()
    {
        int ans = 0;
        fo(val, -x, x)
        {
            fo(i, 1, n) arr[i] = a[i];
            fo(l, 1, n)
            {
                arr[l - 1] = a[l - 1];
                fo(r, l, n)
                {
                    arr[r] = a[r] + x;
                    ans = max(ans, LIS(arr, n));
                }
            }
        }
        cout << ans << "\n";
    }
}
namespace sub4
{
    void solve()
    {
        cout << LIS(a, n);
    }
}
namespace full
{
    BIT t3;
    int l[maxn], r[maxn];
    int ans = 0;
    void solve()
    {
        vi v;
        fo(i, 1, n) v.pb(a[i]);
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        fo(i, 1, n)
        {
            int lb = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
            l[i] = t1.get(lb) + 1;
            t1.up(lb + 1, l[i]);
        }
        fod(i, n, 1)
        {
            int lb = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
            r[i] = t2.get(lb + 1) + 1;
            t2.up(lb, r[i]);
        }
        fo(i, 1, n) v.pb(a[i] + x), v.pb(a[i] + x - 1);
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        // cout << r[3] << "\n";
        fod(i, n, 1)
        {
            int lb = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
            ans = max(ans, l[i] + t3.get(lb));
            // cout << i << ' ' << l[i] << ' ' << t3.get(lb) << "\n";
            lb = lower_bound(v.begin(), v.end(), a[i] + x - 1) - v.begin() + 1;
            t3.up(lb, r[i]);
            ans = max(ans, l[i] + r[i] - 1);
        }
        cout << ans;
    }
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> x;
    fo(i, 1, n) cin >> a[i];
    // if (n <= 1000 and x <= 1000)
    //     sub2::solve();
    // else if  (x == 0)
    //     sub4::solve();
    // else
    full::solve();
}

Compilation message (stderr)

glo.cpp:159:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  159 | main()
      | ^~~~
glo.cpp: In function 'int main()':
glo.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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