Submission #880784

#	Time	Username	Problem	Language	Result	Execution time	Memory
880784		cpptowin	Global Warming (CEOI18_glo)	C++17	25 / 100	277 ms	9044 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 200010
#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;
//     }
// };
struct BIT1
{
    int t[200000];
    void up(int x, int val)
    {
        for (; x < 200000; 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;
        // cout << "xxxx" << "\n";
        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);
    }
}
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];
    // cout << LIS(a,n) << "\n";
    if(n <= 50 and x <= 50) sub2::solve();
    else if(x == 0) sub4::solve();
}

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25