Submission #982634

#	Time	Username	Problem	Language	Result	Execution time	Memory
982634		SmuggingSpun	Global Warming (CEOI18_glo)	C++14	55 / 100	66 ms	10128 KiB

glo

#include<bits/stdc++.h>
#define taskname "glo"
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
const int lim = 2e5 + 5;
const int INF = 2e9 + 1;
int n, X, a[lim];
namespace sub12{
	void solve(){
		int ans = 0;
		for(int i = 1; i <= n; i++){
			for(int j = i; j <= n; j++){
				for(int d = -X; d <= X; d++){
					vector<int>t(n + 1), f(n + 1, INF);
					for(int k = 1; k <= n; k++){
						t[k] = a[k];
					}
					for(int k = i; k <= j; k++){
						t[k] += d;
					}
					f[0] = -INF;
					for(int k = 1; k <= n; k++){
						int low = 0, high = n - 1, p;
						while(low <= high){
							int mid = (low + high) >> 1;
							if(f[mid] < t[k]){
								low = (p = mid) + 1;
							}
							else{
								high = mid - 1;
							}
						}
						f[++p] = t[k];
						maximize(ans, p);
					}
				}
			}
		}	
		cout << ans;	
	}
}
namespace sub4{
	void solve(){
		vector<int>f(n + 1, INF);
		f[0] = -INF;
		int ans = 0;
		for(int k = 1; k <= n; k++){
			int low = 0, high = n - 1, p;
			while(low <= high){
				int mid = (low + high) >> 1;
				if(f[mid] < a[k]){
					low = (p = mid) + 1;
				}
				else{
					high = mid - 1;
				}
			}
			f[++p] = a[k];
			maximize(ans, p);
		}
		cout << ans;
	}
}
namespace sub6{
	int f[lim], p[lim];
	void solve(){
		fill(p, p + lim, INF);
		p[0] = -INF;
		for(int i = 1; i <= n; i++){
			int low = 0, high = n - 1, P;
			while(low <= high){
				int mid = (low + high) >> 1;
				if(p[mid] < a[i]){
					low = (P = mid) + 1;
				}
				else{
					high = mid - 1;
				}
			}
			p[++P] = a[i];
			f[i] = max(f[i - 1], P);
		}
		int ans = f[n];
		fill(p, p + lim, -INF);
		p[0] = INF;
		for(int i = n, pre = 0; i > 0; i--){
			int low = 0, high = n - 1, P;
			a[i] += X;
			while(low <= high){
				int mid = (low + high) >> 1;
				if(p[mid] > a[i]){
					low = (P = mid) + 1;
				}
				else{
					high = mid - 1;
				}
			}
			p[++P] = a[i];
			maximize(ans, (pre = max(pre, P)) + f[i - 1]);
		}
		cout << ans;
	}
}
namespace sub3{
	void solve(){
		int ans = 0;
		for(int i = n; i > 0; a[i--] += X){
			vector<int>f(n + 1, INF);
			f[0] = -INF;
			for(int k = 1; k <= n; k++){
				int low = 0, high = n - 1, p;
				while(low <= high){
					int mid = (low + high) >> 1;
					if(f[mid] < a[k]){
						low = (p = mid) + 1;
					}
					else{
						high = mid - 1;
					}
				}
				f[++p] = a[k];
				maximize(ans, p);
			}
		}
		cout << ans;
	}
}
namespace sub57{
	int N, bit[lim];
	vector<vector<pair<int, int>>>per;
	void roll_back(){
		for(auto& [x, y] : per.back()){
			bit[x] = y;
		}
		per.pop_back();
	}
	void update(int p, int x){
		per.emplace_back(vector<pair<int, int>>());
		for(; p <= N; p += p & -p){
			per.back().emplace_back(make_pair(p, bit[p]));
			maximize(bit[p], p);
		}
	}
	int get(int p){
		int ans = 0;
		for(; p > 0; p -= p & -p){
			maximize(ans, bit[p]);
		}
		return ans;
	}
	void solve(){
		vector<int>compress;
		for(int i = 1; i <= n; i++){
			compress.emplace_back(a[i]);
		}
		compress.emplace_back(-INF);
		N = compress.size();
		compress.emplace_back(INF);
		sort(compress.begin(), compress.end());
		compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
		memset(bit, 0, sizeof(bit));
		vector<int>f(n + 1, INF);
		int ans = f[0] = -INF;
		for(int i = 1; i <= n; i++){
			int low = 0, high = n - 1, p;
			while(low <= high){
				int mid = (low + high) >> 1;
				if(f[mid] < a[i]){
					low = (p = mid) + 1;
				}
				else{
					high = mid - 1;
				}
			}
			maximize(ans, p);
			update(lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin(), p);
		}
		fill(f.begin(), f.end(), -INF);
		f[0] = INF;
		for(int i = n; i > 0; i--){
			roll_back();
			a[i] += X;
			int low = 0, high = n - 1, p;
			while(low <= high){
				int mid = (low + high) >> 1;
				if(f[mid] > a[i]){
					low = (p = mid) + 1;
				}
				else{
					high = mid - 1;
				}
			}
			maximize(ans, get(upper_bound(compress.begin(), compress.end(), a[i]) - compress.begin() - 1) + p);
		}
		cout << ans;
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> X;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	if(n <= 50){
		sub12::solve();
	}
	else if(n <= 1000){
		sub3::solve();
	}
	else if(X == 0){
		sub4::solve();
	}
	else if(X == 1000000000){
		sub6::solve();
	}
	else{
		sub57::solve();
	}
}

Compilation message (stderr)

glo.cpp: In function 'void sub57::roll_back()':
glo.cpp:137:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  137 |   for(auto& [x, y] : per.back()){
      |             ^
glo.cpp: In function 'int main()':
glo.cpp:206:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp: In function 'void sub6::solve()':
glo.cpp:103:6: warning: 'P' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |    p[++P] = a[i];
      |      ^~~
glo.cpp:85:6: warning: 'P' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |    p[++P] = a[i];
      |      ^~~
glo.cpp: In function 'void sub3::solve()':
glo.cpp:126:12: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  126 |     f[++p] = a[k];
glo.cpp: In function 'void sub12::solve()':
glo.cpp:38:14: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |       f[++p] = t[k];
glo.cpp: In function 'void sub4::solve()':
glo.cpp:63:11: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |    f[++p] = a[k];
glo.cpp: In function 'void sub57::solve()':
glo.cpp:198:12: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  198 |    maximize(ans, get(upper_bound(compress.begin(), compress.end(), a[i]) - compress.begin() - 1) + p);
      |    ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:181:10: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  181 |    update(lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin(), p);
      |    ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25