Submission #308147

#	Time	Username	Problem	Language	Result	Execution time	Memory
308147		exopeng	Global Warming (CEOI18_glo)	C++14	28 / 100	2085 ms	6864 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
#define pii pair<int,int>
#define is insert
const long long INF = 10000000000;
const long long MOD = 1000000007;
//store test cases here
/*


*/
int n,x;
long long a[200001];
vector<long long> d;
vector<long long> r;

int f[200001];
int b[200001];

int bsearch(int a) {
	int lo = 0;
	int hi = n-1;
	while (lo != hi) {
		int mid = (lo+hi)/2;
		if (r[mid] < a) {
			hi = mid;
		} else {
			lo = mid+1;
		}
		//cout << lo << "\n";
	} 
	return lo;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x;
    for (int i = 0; i < n; i++) {
    	cin >> a[i];
    	d.pb(INF);
     	r.pb(-1*INF);
    }
    d.pb(INF);
    d[0] = -1*INF;
    r.pb(-1*INF);
    r[0] = INF;
    for (int i = 0; i < n; i++) {
    	int ind = lower_bound(d.begin(),d.end(),a[i]+1) - d.begin();
    	if (d[ind-1] < a[i] && a[i] < d[ind]) {
            d[ind] = a[i];
            f[i] = ind;
    	} else {
    		f[i] = 1;
    	}
    	//cout << "i: " << i << " val: " << f[i] << "\n";
    }
    
    for (int i = n-1; i > -1; i--) {
    	int ind = bsearch(a[i]-1);
    	if (r[ind] < a[i] && a[i] <= r[ind-1]) {
            r[ind] = a[i]-1;
            b[i] = ind;
    	} else {
    		b[i] = 1;
    	}
    	//cout << "i: " << i << " val: " << b[i] << "\n";

    }
	
    int ans = 0;
    for (int i = 0; i <= n; i++) {
    	if (d[i] < INF) {
    		ans = i;
    	}
    }    

    for (int i = n-1; i > 0; i--) {
    	//doesn't have to be next to each other
    	for (int j = i-1; j > -1; j--) {
    		if (a[i] <= a[j] && a[j] - a[i] < x) {
	    		ans = max(ans,f[j] + b[i]);
	    	}
    	}
    }
    cout << ans << "\n";


}
/* REMINDERS
 * CHECK ARRAY BOUNDS, HOW BIG ARRAY HAS TO BE
 * PLANNING!!!!!!!! Concrete plan before code
 * IF CAN'T FIGURE ANYTHING OUT, MAKE TEN TEST CASES TO EVALUATE ALL TYPES OF SCENARIOS, THEN CONSTRUCT SOLUTION TO FIT IT
 * IF CAN'T FIGURE ANYTHING OUT, MAKE TEN TEST CASES TO EVALUATE ALL TYPES OF SCENARIOS, THEN CONSTRUCT SOLUTION TO FIT IT
 * IF CAN'T FIGURE ANYTHING OUT, MAKE TEN TEST CASES TO EVALUATE ALL TYPES OF SCENARIOS, THEN CONSTRUCT SOLUTION TO FIT IT
 * NAIVE SOL FIRST TO CHECK AGAINST OPTIMIZED SOL
 * MOD OUT EVERY STEP
 * DON'T MAKE ASSUMPTIONS
 * DON'T OVERCOMPLICATE
 * CHECK INT VS LONG, IF YOU NEED TO STORE LARGE NUMBERS
 * CHECK CONSTRAINTS, C <= N <= F...
 * CHECK SPECIAL CASES, N = 1...
 * TO TEST TLE/MLE, PLUG IN MAX VALS ALLOWED AND SEE WHAT HAPPENS
 * ALSO CALCULATE BIG-O, OVERALL TIME COMPLEXITY
 * IF ALL ELSE FAILS, DO CASEWORK
 * compile with "g++ -std=c++11 filename.cpp" if using auto keyword
 */

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