Submission #1294659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294659		herominhsteve	Money (IZhO17_money)	C++20	100 / 100	380 ms	12188 KiB

money

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "IZhO17_money"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

template<typename T>
struct HaviTree{
	int n;
	vector<T> havi;
	HaviTree(int N=0){
		n=N;
		if (n>0){
			havi.resize(n+1,0);
		}
	}
	void update(int node,T val){
		while (node<=n){
			havi[node]+=val;
			node += (node & -node);
		}
	}
	T getVal(int node){
		T res=0;
		while (node>0){
			res+=havi[node];
			node -= (node & -node);
		}
		return res;
	}
	inline T range(int l,int r){
		return getVal(r) - getVal(l-1); 
	}
};

int n,m;
vector<int> a;

void init(){
	cin>>n;
	a.assign(n+1,0);
	vector<int> org(n);
	for (int &x : org) cin>>x;
	vector<int> compress(allof(org));
	sort(allof(compress));
	compress.resize(unique(allof(compress))-compress.begin());
	for (int i=1;i<=n;i++)
		a[i] = lower_bound(allof(compress),org[i-1]) - compress.begin() + 1;
	m = compress.size();
}

void sol(){
	// ? dp[i]: minimum block needed to partition a[1...i]
	vector<int> dp(n+1,0);
	HaviTree<int> havi(m);

	int l = 1;
	for (int r = 1; r <= n; r++){
		/*
		 * if there exist any value outside of this window -> we have to put it inside
		 * thus +1 block
		*/
		while (havi.range(a[l]+1,a[r]-1) > 0){
			havi.update(a[l++],1);
		}
		dp[r] = dp[l-1] + 1;
		if (r < n and a[r+1] < a[r]){
			// * exist an inversion, hence this is the end of this block
			for (int k=l;k<=r;k++) havi.update(a[k],1);
			l = r + 1;
		}
	}
	cout<<dp[n];
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

money.cpp: In function 'void setup()':
money.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
money.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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