Submission #1094986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094986		TVSown	Global Warming (CEOI18_glo)	C++17	100 / 100	46 ms	6112 KiB

glo

///*** Sown_Vipro ***///
/// ->GIAI BA QUOC GIA<- ///

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
#define szz(s) int(s.size())
const int N = 1e6 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
int n, x, res;
int a[N], m[N];
vector<int> L;
void solve(){
    cin >> n >> x;
    for(int i = 1; i <= n; ++i) cin >> a[i];

    L.pb(a[1]); m[1] = 1;
    for(int i = 2; i <= n; ++i){
        if(a[i] > L.back()){
            L.pb(a[i]);
            m[i] = L.size();
        }else{
            int id = lower_bound(L.begin(), L.end(), a[i]) - L.begin();
            L[id] = a[i];
            m[i] = id + 1;
        }
//        cout << m[i] << " ";
    }
    res = L.size();

    L.clear(); L.pb(a[n]);
    for(int i = n - 1; i >= 1; --i){
        int l = 0, r = L.size() - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(L[mid] > a[i] - x){
                l = mid + 1;
            }else r = mid - 1;
        }
        res = max(res, m[i] + r + 1);

        if(a[i] < L.back()){
            L.pb(a[i]);
        }else{
            int l = 0, r = L.size() - 1;
            while(l <= r){
                int mid = (l + r) / 2;
                if(L[mid] <= a[i]){
                    r = mid - 1;
                }else l = mid + 1;
            }
            L[l] = a[i];
        }

//        for(int x : L) cout << x << " ";
//        cout << "\n";
    }
    cout << res;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    inp("in.txt");
    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:14:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~
glo.cpp:72:5: note: in expansion of macro 'inp'
   72 |     inp("in.txt");
      |     ^~~

• 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