Submission #468237

#	Time	Username	Problem	Language	Result	Execution time	Memory
468237		wdjpng	Global Warming (CEOI18_glo)	C++17	17 / 100	123 ms	7388 KiB

glo

#include <bits/stdc++.h>

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)

using namespace std;

signed main()
{
    int n, x;
    cin >> n >> x;
    vector<int>t(n);
    rep(i,n) cin>>t[i];

    vector<int>c;
    vector<int>right(n);
    for(int i = n-1; i >=0; i--)
    {
        int r = 1e10 - t[i];
        if(!c.size()||r>c[c.size()-1]) c.push_back(r);
        else *(lower_bound(c.begin(), c.end(), r)) = r;
        right[i] = c.size();
    }
    c = vector<int>(n, 1e17);
    
    int maxx = 0;
    rep(i,n)
    {
        auto it  = lower_bound(c.begin(), c.end(), t[i] - x);
        int off = it - c.begin();
        maxx=max(maxx, right[i] + (lower_bound(c.begin(), c.end(), t[i]) - c.begin()));
        *(lower_bound(c.begin(), c.end(), t[i]-x)) = t[i] - x;
    }
    cout<<maxx<<"\n";
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:30:13: warning: unused variable 'off' [-Wunused-variable]
   30 |         int off = it - c.begin();
      |             ^~~

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