oj.uz

Submission #940031

# Submission time Handle Problem Language Result Execution time Memory
940031 2024-03-07T04:21:32 Z vjudge1 Global Warming (CEOI18_glo) C++17
45 / 100
 83 ms 9020 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int INF = 1e9 + 7;
int LIS(vector<int> a){
	 
	set<int> dp;
	for(int i = 0;i < (int)a.size(); i++){		
		int x = a[i];
		if(dp.lower_bound(x) != dp.end()) dp.erase(dp.lower_bound(x));
		dp.insert(x);
	}
	return (int)dp.size();
} 

main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
	int x; cin >> x;
	vector<int> a(n), b(n);
	for(int i = 0;i < n; i++){
		cin >> a[i];
		b[i] = -a[i];
	}
	vector<int> suf(n+1, INF), suf_ans(n, 0);
	suf[0] = -INF;
	for(int i = n-1; i >= 0; i--){
		int j = upper_bound(all(suf), b[i]) - suf.begin();
		if(suf[j-1] < b[i] && b[i] < suf[j]){
			suf_ans[i] = max(suf_ans[i], j);
			suf[j] = b[i];
		}
	}
	
	int ans = LIS(a);
	vector<int> dp(n + 1, INF), pref_ans(n, 0);
	dp[0] = -INF;
	for(int i = 0;i < n; i++){
		int j = int(upper_bound(dp.begin(), dp.end(), a[i])  - dp.begin());
		if(dp[j - 1] < a[i] and a[i] < dp[j]){
			dp[j] = a[i];
			pref_ans[i] = max(pref_ans[i], j);
		} 
		if(i + 1 < n){
			int d = a[i + 1] + x;
			int it = upper_bound(all(dp), d) - dp.begin();
			if(dp[it-1] < d){
				ans = max(ans, suf_ans[i+1] + it-1);
			}
		}
		
	}
	
	
	
	cout << ans;
    return 0;
}

Compilation message

glo.cpp:18:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   18 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 1 ms 344 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 5152 KB Output is correct
2 Correct 79 ms 5192 KB Output is correct
3 Correct 78 ms 5200 KB Output is correct
4 Correct 83 ms 5072 KB Output is correct
5 Correct 69 ms 9020 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1432 KB Output is correct
2 Correct 19 ms 1432 KB Output is correct
3 Correct 19 ms 1432 KB Output is correct
4 Correct 16 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 18 ms 2396 KB Output is correct
7 Correct 15 ms 1436 KB Output is correct

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 1 ms 344 KB Output isn't correct
20 Halted 0 ms 0 KB -