oj.uz

답안 #737200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
737200 2023-05-06T18:40:38 Z MODDI Global Warming (CEOI18_glo) C++14
100 / 100
 1136 ms 101068 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
#define se second
#define fi first
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
ll set_on(ll n, ll k){
	return (n |= 1 << k);
}
ll set_off(ll n, ll k){
	return (n &= ~(1UL << k));
}
bool check_bit(ll n, ll k){
	int bit = (n >> k) & 1U;
	if(bit == 1)
		return true;
	return false;
}
const ll INF = 1e9;
int n;
ll x;
int tree[4 * 600010];
void update(int node, int l, int r, int pos, int val){
	if(l == r && l == pos){
		tree[node] = max(tree[node], val);
	}
	else{
		int mid = (l + r) / 2;
		if(pos <= mid)
			update(node * 2, l, mid, pos, val);
		else
			update(node * 2 + 1, mid + 1, r, pos, val);
		
		tree[node] = max(tree[node*2], tree[node * 2 + 1]);
	}
}
int query(int node, int l, int r, int L, int R){
	if(r < L || l > R)	return 0;
	if(L <= l && r <= R)	return tree[node];
	
	int mid = (l + r) / 2;
	int left = query(node * 2, l, mid, L, R);
	int right = query(node * 2 + 1, mid + 1, r, L, R);
	return max(left, right);
}
void solve(){
	cin>>n>>x;
	vl arr(n);
	set<ll> nums;
	for(auto &s : arr)
	{
		cin>>s;
		nums.insert(s);
		nums.insert(max(s - x + 1, 0LL));
		nums.insert(min(s + x - 1, INF));
	}
	map<int,int> compress, rev_compress;
	int id = 1;
	for(auto t : nums){
		compress[t] = id;
		rev_compress[id] = t;
		id++;
	}
	int start[n], end[n];
	for(int i = 0; i < n; i++){
		start[i] = end[i] = 1;
	}
	vi d(n+1, INF);
	vi pos(n+1, -1);
	d[0] = -INF;
	for(int i = 0; i < n; i++){
		int l = upper_bound(d.begin(), d.end(), arr[i]) - d.begin();
		if(d[l-1] < arr[i] && arr[i] < d[l]){
			d[l] = arr[i];
			end[i] = l;
		}
	}
	for(int i = 0; i < arr.size(); i++)
		arr[i] *= -1;
	reverse(arr.begin(), arr.end());
	d.resize(n+1, INF);
	d[0] = -INF;
	for(int i = 0; i < n; i++){
		int l = upper_bound(d.begin(), d.end(), arr[i]) - d.begin();
		if(d[l-1] < arr[i] && arr[i] < d[l]){
			d[l] = arr[i];
			start[i] = l;
		}
	}
	reverse(arr.begin(),arr.end());
	for(int i = 0, j = n - 1; i < j; i++, j--){
		swap(start[i], start[j]);
	}
	for(int i = 0; i < arr.size(); i++)
		arr[i] *= -1;
	int ans = 0;
	for(int i = 0; i < n; i++){
		ans = max(ans, end[i]);
		ans = max(ans, start[i]);
	}
	memset(tree, 0, sizeof tree);
	for(int i = n - 1; i > 0; i--){
		update(1, 0, id, compress[arr[i]], start[i]);
		int left = compress[max(arr[i-1]-x + 1, 0LL)], right = compress[min(arr[i-1]+x-1, INF)];
		int best = query(1, 0, id, left, right);
//		debug(left, right, best, end[i-1], left, right);
		ans = max(ans, best + end[i-1]);
	}
	cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(10);
	cout<<fixed;
	startTime = clock();
	int t=1;
//	cin>>t;
	while(t--)
		solve();

	return 0;
}

Compilation message

glo.cpp: In function 'void solve()':
glo.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for(int i = 0; i < arr.size(); i++)
      |                 ~~^~~~~~~~~~~~
glo.cpp:129:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |  for(int i = 0; i < arr.size(); i++)
      |                 ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9668 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 4 ms 9608 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9668 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 4 ms 9608 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 4 ms 9684 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 4 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9668 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 4 ms 9608 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 4 ms 9684 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 4 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 6 ms 10068 KB Output is correct
20 Correct 7 ms 10068 KB Output is correct
21 Correct 7 ms 10068 KB Output is correct
22 Correct 7 ms 10068 KB Output is correct
23 Correct 5 ms 9940 KB Output is correct
24 Correct 6 ms 9940 KB Output is correct
25 Correct 5 ms 9812 KB Output is correct
26 Correct 5 ms 9812 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 986 ms 100844 KB Output is correct
2 Correct 968 ms 100884 KB Output is correct
3 Correct 1031 ms 100844 KB Output is correct
4 Correct 961 ms 100992 KB Output is correct
5 Correct 332 ms 57924 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 32444 KB Output is correct
2 Correct 187 ms 32460 KB Output is correct
3 Correct 171 ms 32396 KB Output is correct
4 Correct 78 ms 21676 KB Output is correct
5 Correct 4 ms 9616 KB Output is correct
6 Correct 57 ms 14560 KB Output is correct
7 Correct 127 ms 27864 KB Output is correct

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 27088 KB Output is correct
2 Correct 232 ms 27220 KB Output is correct
3 Correct 554 ms 44600 KB Output is correct
4 Correct 255 ms 29772 KB Output is correct
5 Correct 160 ms 26756 KB Output is correct
6 Correct 327 ms 42148 KB Output is correct
7 Correct 310 ms 42804 KB Output is correct
8 Correct 182 ms 27028 KB Output is correct

Subtask #7
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9668 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 4 ms 9608 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 4 ms 9684 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 4 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 6 ms 10068 KB Output is correct
20 Correct 7 ms 10068 KB Output is correct
21 Correct 7 ms 10068 KB Output is correct
22 Correct 7 ms 10068 KB Output is correct
23 Correct 5 ms 9940 KB Output is correct
24 Correct 6 ms 9940 KB Output is correct
25 Correct 5 ms 9812 KB Output is correct
26 Correct 5 ms 9812 KB Output is correct
27 Correct 986 ms 100844 KB Output is correct
28 Correct 968 ms 100884 KB Output is correct
29 Correct 1031 ms 100844 KB Output is correct
30 Correct 961 ms 100992 KB Output is correct
31 Correct 332 ms 57924 KB Output is correct
32 Correct 189 ms 32444 KB Output is correct
33 Correct 187 ms 32460 KB Output is correct
34 Correct 171 ms 32396 KB Output is correct
35 Correct 78 ms 21676 KB Output is correct
36 Correct 4 ms 9616 KB Output is correct
37 Correct 57 ms 14560 KB Output is correct
38 Correct 127 ms 27864 KB Output is correct
39 Correct 202 ms 27088 KB Output is correct
40 Correct 232 ms 27220 KB Output is correct
41 Correct 554 ms 44600 KB Output is correct
42 Correct 255 ms 29772 KB Output is correct
43 Correct 160 ms 26756 KB Output is correct
44 Correct 327 ms 42148 KB Output is correct
45 Correct 310 ms 42804 KB Output is correct
46 Correct 182 ms 27028 KB Output is correct
47 Correct 436 ms 55360 KB Output is correct
48 Correct 446 ms 55340 KB Output is correct
49 Correct 1136 ms 101068 KB Output is correct
50 Correct 338 ms 57776 KB Output is correct
51 Correct 248 ms 35228 KB Output is correct
52 Correct 343 ms 43980 KB Output is correct
53 Correct 346 ms 43800 KB Output is correct
54 Correct 332 ms 44492 KB Output is correct
55 Correct 662 ms 82320 KB Output is correct