Submission #1104612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104612		Shadow1	Mountains (NOI20_mountains)	C++17	100 / 100	685 ms	48228 KiB

Mountains

// Programmer: Shadow1

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using str = string; // yay python!

#define i64 int64_t
#define watch(x) cerr << (#x) << " = " << (x) << '\n';
#define output_vector(v) for(auto &x : v){cout << x << " ";}cout << '\n';
#define vt vector
#define st stack
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define umap unordered_map
#define uset unordered_set
#define fir first
#define sec second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


// T: O(n log n)
// M : O(n + k log n)

class FenwickTree {
private:
	vector<int64_t> ft;
public:
	FenwickTree(int m) {  // Create empty Fenwick Tree
		ft.assign(m+1,0);
	}

	int LSOne(int x) {    // Return Least significant 1-bit of x
		return ((x) & (-x));
	}
	void build(const vector<int64_t> &f) {  // Build the fenwick tree array from the frequency array
		int m = sz(f) - 1;
		ft.assign(m+1,0);
		for(int i=1; i<=m; ++i) {
			ft[i] += f[i];
			if(i + LSOne(i) <= m)
				ft[i+LSOne(i)] += ft[i];
		}
	}

	FenwickTree(int m, const vector<int64_t> &s) {   // Convert the array to a frequency array with m integer keys
		vector<int64_t> f(m+1,0);						// i.e. the array's maximum value must be m
		for(int i=0; i<sz(s); ++i)
			++f[s[i]];
	}

	int64_t rsq(int i, int j) {  // i <= j   // O(log m)
		int64_t sum = 0;
		while(j > 0) {
			sum += ft[j];
			j -= LSOne(j);
		}
		--i;
		while(i > 0) {
			sum -= ft[i];
			i -= LSOne(i);
		}
		return sum;
	}

	void update(int i, int64_t v) {
		for(; i<sz(ft); i+=LSOne(i))   // O(log m)
			ft[i] += v;
	}

};


void solve() {
	int n;
	cin >> n;
	vector<int64_t> h(n), cnt(n+1), p(n+1); // cnt[i] is the number of ith smallest elements.
	set<int64_t> s;
	map<int64_t, int> rank;

	for(int i=0; i<n; ++i) {  // O(n log n)
		cin >> h[i];
		s.insert(h[i]);
	}
	int k = 1;
	for(auto &S : s) {  // Worse case O(n log n)
		rank[S] = k;     // S is the kth smallest element
		++k;
	}
	--k;
	assert(k <= n);
	for(auto &H : h) 
		cnt[rank[H]]++;   
	
	p[1] = cnt[1];
	for(int i=2; i<=k; ++i)
		p[i] = p[i-1] + cnt[i];

	// Algorithm starts: 
	FenwickTree ft(k);  // ft[i] will contain the number of ith smallest elements
	int64_t ans = 0;
	
	ft.update(rank[h[0]],1);
	for(int i=1; i<n-1; ++i) {
		int64_t x = ft.rsq(1,rank[h[i]]-1);    // O(log n)	
		int64_t y = p[rank[h[i]]-1];
		ans += (x * (y - x));
		ft.update(rank[h[i]],1);  // update
	}
	cout << ans << '\n';
}

int main() {
	// freopen("output.txt", "w", stdout);
	// freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	
	solve();
	return 0;
}

/* CHECK :
1. COMPARATOR FUNCTION MUST RETURN FALSE WHEN ARGUMENTS ARE EQUAL!!!
2. Overflow! Typecase int64_t on operations if varaibles are int
3. Check array bounds!!!
4. Check array indexing!!!
5. Edge cases. (N==1)!!!
*/

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 9 / 9
• Subtask 7: 12 / 12