Submission #1141315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141315		SmuggingSpun	Financial Report (JOI21_financial)	C++20	100 / 100	2245 ms	116440 KiB

Main

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
const int INF = 1e9;
template<class T>bool maximize(T& a, T b){
	if(a < b){
		a = b;
		return true;
	}
	return false;
}
int n, d;
namespace sub1{
	void solve(){
		vector<int>a(n);
		for(int& x : a){
			cin >> x;
		}
		int ans = 0;
		for(int mask = (1 << n) - 1; mask > 0; mask--){
			vector<int>index;
			for(int i = 0; i < n; i++){
				if(1 << i & mask){
					if(!index.empty() && i - index.back() > d){
						index.clear();
						break;
					}
					index.emplace_back(i);
				}
			}
			if(!index.empty() && index.back() == n - 1){
				int cnt = 0, cur_max = -1;
				for(int& x : index){
					if(maximize(cur_max, a[x])){
						cnt++;
					}
				}
				maximize(ans, cnt);
			}
		}
		cout << ans;
	}
}
namespace sub2{
	void solve(){
		vector<int>a(n);
		for(int& x : a){
			cin >> x;
		}
		vector<vector<int>>dp(n, vector<int>(n, -INF));
		for(int i = 0; i < n; i++){
			maximize(dp[i][i], 1);
			for(int j = i; j > -1; j--){
				for(int k = min(n - 1, i + d); k > i; k--){
					if(a[k] > a[j]){
						maximize(dp[k][k], dp[i][j] + 1);
					}
					else{
						maximize(dp[k][j], dp[i][j]);
					}
				}
			}
		}
		cout << *max_element(dp[n - 1].begin(), dp[n - 1].end());
	}
}
namespace sub3{
	void solve(){
		vector<int>a(n);
		for(int& x : a){
			cin >> x;
		}
		vector<int>dp(n, 1);
		for(int i = n - 2; i > -1; i--){
			for(int j = i + 1, pre = i; j < n && j - pre <= d; j++){
				if(a[j] > a[i]){
					maximize(dp[i], dp[j] + 1);
				}			
				else{
					pre = j;
				}	
			}
		}
		cout << *max_element(dp.begin(), dp.end());
	}
}
namespace sub4{
	void solve(){
		vector<int>a(n);
		for(int& x : a){
			cin >> x;
		}
		vector<int>dp(n + 1);
		dp[n] = 0;
		stack<int>st;
		for(int i = n - 1; i > -1; st.push(i--)){
			while(!st.empty() && a[st.top()] <= a[i]){
				st.pop();
			}
			dp[i] = dp[st.empty() ? n : st.top()] + 1;
		}
		cout << *max_element(dp.begin(), dp.end());
	}
}
namespace sub5{
	const int LIM = 1e9 + 5;
	void solve(){
		map<int, int>bit;
		auto update = [&] (int p, int x){
			for(p++; p < LIM; p += p & -p){
				maximize(bit[p], x);
			}
		};
		auto get = [&] (int p){
			int ans = 0;
			for(; p > 0; p -= p & -p){
				auto it = bit.find(p);
				if(it != bit.end()){
					maximize(ans, it->second);
				}
			}	
			return ans;
		};
		for(int i = 0; true; i++){
			int x;
			cin >> x;
			int LIS = get(x) + 1;
			update(x, LIS);
			if(i + 1 == n){
				cout << get(LIM - 1);
				break;
			}
		}
	}
}
namespace sub6{
	const int lim = 3e5 + 5;
	struct Data{
		int len, sum, left, right, opt;
		Data(){}
		Data(int _len, int _sum, int _left, int _right, int _opt) : len(_len), sum(_sum), left(_left), right(_right), opt(_opt) {}
	};
	Data st_sum[lim << 2];
	int a[lim], st_max[lim << 2];
	void build(int id, int l, int r){
		st_sum[id] = Data(r - l + 1, 0, 0, 0, 0);
		if(l < r){
			int m = (l + r) >> 1;
			build(id << 1, l, m);
			build(id << 1 | 1, m + 1, r);
		}
	}
	Data merge_sum(Data l, Data r){
		if(l.len == -1){
			return r;
		}
		if(r.len == -1){
			return l;
		}
		return Data(l.len + r.len, l.sum + r.sum, max(l.left, l.len == l.sum ? l.sum + r.left : 0), max(r.right, r.len == r.sum ? r.sum + l.right : 0), max(max(l.opt, r.opt), l.right + r.left));
	}
	void update_sum(int id, int l, int r, int p){
		if(l == r){
			st_sum[id] = Data(1, 1, 1, 1, 1);
			return;
		}	
		int m = (l + r) >> 1;
		if(m < p){
			update_sum(id << 1 | 1, m + 1, r, p);
		}
		else{
			update_sum(id << 1, l, m, p);
		}
		st_sum[id] = merge_sum(st_sum[id << 1], st_sum[id << 1 | 1]); 
	}
	Data get_sum(int id, int l, int r, int u, int v){
		if(l > v || r < u){
			return Data(-1, 0, 0, 0, 0);
		}
		if(u <= l && v >= r){
			return st_sum[id];
		}
		int m = (l + r) >> 1;
		return merge_sum(get_sum(id << 1, l, m, u, v), get_sum(id << 1 | 1, m + 1, r, u, v));
	}
	void update_max(int id, int l, int r, int p, int x){
		if(l == r){
			st_max[id] = x;
			return;
		}
		int m = (l + r) >> 1;
		if(m < p){
			update_max(id << 1 | 1, m + 1, r, p, x);
		}
		else{
			update_max(id << 1, l, m, p, x);
		}
		st_max[id] = max(st_max[id << 1], st_max[id << 1 | 1]);
	}
	int get_max(int id, int l, int r, int u, int v){
		if(l > v || r < u){
			return 0;
		}
		if(u <= l && v >= r){
			return st_max[id];
		}
		int m = (l + r) >> 1;
		return max(get_max(id << 1, l, m, u, v), get_max(id << 1 | 1, m + 1, r, u, v));
	}
	void solve(){
		for(int i = 1; i <= n; i++){
			cin >> a[i];
		}
		build(1, 1, n);
		vector<int>p(n);
		iota(p.begin(), p.end(), 1);
		sort(p.begin(), p.end(), [&] (int i, int j) -> bool{
			return a[i] > a[j] || (a[i] == a[j] && i < j);
		});
		memset(st_max, 0, sizeof(st_max));
		for(int& i : p){
			if(i == n){
				update_sum(1, 1, n, n);
				update_max(1, 1, n, n, 1);
				continue;
			}
			int low = i + 1, high = n, last = i;
			while(low <= high){
				int mid = (low + high) >> 1;
				if(get_sum(1, 1, n, i + 1, mid).opt < d){
					low = (last = mid) + 1;
				}
				else{
					high = mid - 1;
				}
			}
			update_sum(1, 1, n, i);
			update_max(1, 1, n, i, get_max(1, 1, n, i + 1, min(n, last + 1)) + 1);
		}
		cout << st_max[1];
	}
}
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 >> d;
	if(n <= 20){
		sub1::solve();
	}
	else if(n <= 400){
		sub2::solve();
	}
	else if(n <= 7000){
		sub3::solve();
	}
	else if(d == 1){
		sub4::solve();
	}
	else if(d == n){
		sub5::solve();
	}
	else{
		sub6::solve();
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:246:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  246 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35