Submission #467133

#	Time	Username	Problem	Language	Result	Execution time	Memory
467133		wind_reaper	Money (IZhO17_money)	C++17	0 / 100	0 ms	204 KiB

money

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


using namespace std;
using namespace __gnu_pbds;
using namespace chrono;

#define dbg(x) cout << "[" << #x << ' ' << x << "] ";

// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;


//***************** CONSTANTS *****************

const int MXN = 1'00;
const int MXK = 20;

//***************** GLOBAL VARIABLES *****************

int A[MXN], diff[MXN], N;

//***************** AUXILIARY STRUCTS *****************

template<typename T>
struct SparseTable{
	int st[MXK][MXN];
	int log[MXN];

	function<T(const T&,const T&)> merge;

	SparseTable(const function<T(const T&, const T&)>& _merge){
		merge = _merge;

		log[0] = log[1] = 0;
		for(int i = 2; i <= N; i++)
			log[i] = log[i>>1] + 1;

		for(int i = 0; i < N; i++)
			st[0][i] = diff[i];

		for(int j = 1; j < MXK; j++){
			for(int i = 0; i + (1 << j) <= N; i++)
				st[j][i] = merge(st[j-1][i], st[j-1][i + (1 << (j-1))]);
		}
	}

	int query(int L, int R){
		int j = log[R - L + 1];

		if(R > N)
			return -1;

		return merge(st[j][L], st[j][R - (1 << j) + 1]);
	}
};

//***************** MAIN BODY *****************

void solve(){
	cin >> N;

	for(int i = 1; i <= N; i++){
		cin >> A[i];
		diff[i] = A[i] - A[i-1];
		// cout << diff[i] << ' ';
	}

	SparseTable<int> st([](int a, int b){return min(a, b); });

	// function<int(const int&)> find = [&](const int& i) -> int {
	// 	int lo = i + 1, hi = N, ans = i + 1;
	// 	while(lo <= hi){
	// 		int mid = (lo + hi) >> 1;
	// 		if(st.query(i + 1, mid) >= 0){
	// 			ans = mid;
	// 			lo = mid + 1;
	// 		}
	// 		else hi = mid - 1;
	// 	}

	// 	return A[ans] > A[ans - 1] ? ans : ans - 1;
	// };

	function<int(const int&)> find = [&](const int& i) -> int {
		int j;
		for(j = i + 1; j <= N; j++)
			if(A[j] < A[j - 1])
				return j - 1;
	};

	// find the min j such that A[j...i] is non decreasing, use a sparse table on a diff array to find minimum j such that min of \
	diff is >= 0
	
	// then use pbds to find the number of segments this needs to be broken into
	ordered_set<pair<int, int>>	s;
	// overall approach is nlogn
	
	int ans = 0;

	for(int i = 1; i <= N;){
		int j = find(i);
		int inc = s.order_of_key({A[j], -1}) - s.order_of_key({A[i], i}) + 1;
		ans += inc;
		// dbg(j) dbg(i) dbg(ans) dbg(inc) dbg(s.order_of_key({A[j], j})) dbg(s.order_of_key({A[i], i})) cout << '\n';
		for(; i <= j; i++)
			s.insert({A[i], i});
	}

	cout << ans << '\n';

}

//***************** *****************

int32_t main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);

	#ifdef LOCAL
		auto begin = high_resolution_clock::now();
	#endif

	int tc = 1;
	// cin >> tc; 
	for (int t = 0; t < tc; t++)
		solve();

	#ifdef LOCAL 
		auto end = high_resolution_clock::now();
		cout << fixed << setprecision(4);
		cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
	#endif

	return 0;
}

/*
If code gives a WA, check for the following : 
1. I/O format

2. Are you clearing all global variables in between tests if multitests are a thing

3. Can you definitively prove the logic

4. If the code gives an inexplicable TLE, and you are sure you have the best possible complexity,
use faster io
*/

/*
dp[i] -> minimum no. of subarrays to break into to finish this job

if a subsegment is purely increasing in nature, the number of 

3 6  -> 3 3 7

use an ordered set

*/

Compilation message (stderr)

money.cpp:96:2: warning: multi-line comment [-Wcomment]
   96 |  // find the min j such that A[j...i] is non decreasing, use a sparse table on a diff array to find minimum j such that min of \
      |  ^
money.cpp: In lambda function:
money.cpp:94:2: warning: control reaches end of non-void function [-Wreturn-type]
   94 |  };
      |  ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55