oj.uz

Submission #948540

# Submission time Handle Problem Language Result Execution time Memory
948540 2024-03-18T07:47:00 Z dio_2 Global Warming (CEOI18_glo) C++17
0 / 100
 2000 ms 25696 KB 
#include<bits/stdc++.h>
using namespace std;

struct MaxSegree{
	MaxSegree () {}
	MaxSegree (int N){
		build(N);
	}
	int base;
	const int neutral = -(int)1e9;
	vector<int> maxy;
	
	void build(int N){
		base = 1;
		while(base <= N) base *= 2;
		maxy.assign(2 * base, neutral);
	}
	
	void pull(int node){
		maxy[node] = max(maxy[2 * node], maxy[2 * node + 1]);
	}
	
	void update(int node, int lx, int rx, int pos, int val){
		if(lx == rx){
			assert(lx == pos);
			maxy[node] = val;
			return ;
		}
		int mid = (lx + rx) / 2;
		if(pos <= mid){
			update(2 * node, lx, mid, pos, val);
		} else {
			update(2 * node + 1, mid + 1, rx, pos, val);
		}
		pull(node);
	}
	
	int Max(int node, int lx, int rx, int l, int r){
		if(lx > r || rx < l) return neutral;
		if(l <= lx && rx <= r) return maxy[node];
		int mid = (lx + rx) / 2;
		return max(Max(2 * node, lx, mid, l, r), Max(2 * node + 1, mid + 1, rx, l, r));
	}
	
	void update(int pos, int val){
		update(1, 1, base, pos, val);
	}
	
	int Max(int l, int r){
		return Max(1, 1, base, l, r);
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, x;
	cin >> n >> x;
	
	vector<int> t(n);
	set<int> s;
	map<int, int> comp;
	for(int &y : t){
		cin >> y;
		s.insert(y);
	}
	
	// compress for RMQ.
	int cnt = 1;
	for(int y : s){
		comp[y] = cnt++;
	}
	
	MaxSegree LIS(n), LDS(n);
	vector<int> dp(n, 1), dp2(n, 1);
	for(int i = 0;i < n;i++){
		if(comp[t[i]] - 1 >= 1){
			dp[i] = max(dp[i], LIS.Max(1, comp[t[i]] - 1) + 1);
		}
		LIS.update(comp[t[i]], dp[i]);
	}
	
	int answer = dp.back();
	if(x == 0){
		cout << answer << '\n';
		return 0;
	}
	for(int i = n - 1;i >= 0;i--){
		if(comp[t[i]] + 1 <= n){
			dp2[i] = max(dp2[i], LDS.Max(comp[t[i]] + 1, n) + 1);
		}
		LDS.update(comp[t[i]], dp2[i]);
		answer = max(answer, dp2[i]);
		if(i - 1 >= 0){
			int prev_val = t[i - 1] - x;
			// find first strictly <
			for(int j = i;j < n;j++){
				if(prev_val < t[j]){
					answer = max(answer, dp[i - 1] + dp2[j]);
				}
			}
		}
	}
	

	cout << answer << '\n';
	
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2013 ms 6768 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 2041 ms 12880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -