oj.uz

Submission #308147

# Submission time Handle Problem Language Result Execution time Memory
308147 2020-09-30T06:08:35 Z exopeng Global Warming (CEOI18_glo) C++14
28 / 100
 2000 ms 6864 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 6864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2043 ms 2292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 3696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Execution timed out 2085 ms 6864 KB Time limit exceeded
28 Halted 0 ms 0 KB -