oj.uz

Submission #481752

# Submission time Handle Problem Language Result Execution time Memory
481752 2021-10-21T15:07:44 Z BackNoob Global Warming (CEOI18_glo) C++14
15 / 100
 34 ms 3912 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define mask(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
using namespace std;
const int mxN = 3e5 + 227;
const ll inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
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;
}

int n , x; 
int a[mxN];
int l[mxN];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("task.inp" , "r" , stdin);
    //freopen("task.out" , "w" , stdout);
    
    cin >> n >> x;
    for(int i = 1 ; i <= n ; i++) cin >> a[i];

    int res = 0;
    vector<int> lis;
	for(int i = 1 ; i <= n ; i++) {
		int pos = lower_bound(lis.begin() , lis.end() , a[i]) - lis.begin();
		l[i] = pos + 1;
		if(pos == (int) lis.size()) lis.push_back(a[i]);
		else lis[pos] = a[i];
		maximize(res , l[i]);
	}
 	
	lis.clear();

	for(int i = n ; i >= 1 ; i--) {
		int pos = lower_bound(lis.begin() , lis.end() , -(a[i] - x)) - lis.begin();
		maximize(res , l[i] + pos);

		pos = lower_bound(lis.begin() , lis.end() , -a[i]) - lis.begin();
		if(pos == (int) lis.size()) lis.push_back(-a[i]);
		else l[pos] = -a[i];
	}

	cout << res;

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 320 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Incorrect 0 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 320 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Incorrect 0 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3768 KB Output is correct
2 Correct 32 ms 3804 KB Output is correct
3 Correct 32 ms 3748 KB Output is correct
4 Correct 34 ms 3912 KB Output is correct
5 Correct 20 ms 3556 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1100 KB Output is correct
2 Correct 9 ms 1208 KB Output is correct
3 Correct 10 ms 1208 KB Output is correct
4 Incorrect 5 ms 1228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 320 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Incorrect 0 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -