Submission #499376

#	Time	Username	Problem	Language	Result	Execution time	Memory
499376		sumit_kk10	Mountains (NOI20_mountains)	C++17	100 / 100	123 ms	32584 KiB

Mountains

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) 
using namespace std;
const int N = 1e6 + 5;
int n, fenwick[N];

void upd(int x, int val){
	for(int i = x; i < N; i += (i & -i))
		fenwick[i] += val;
}

int get(int x){
	int ans = 0;
	for(int i = x; i >= 1; i -= (i & -i))
		ans += fenwick[i];
	return ans;
}

void solve(){
	cin >> n;
	vector<pair<long long, int> > v(n);
	for(int i = 0; i < n; ++i){
		cin >> v[i].first;
		v[i].second = i;
	}
	vector<long long> a(n);
	sort(v.begin(), v.end());
	int ct = 1;
	a[v[0].second] = ct;
	for(int i = 1; i < n; ++i){
		if(v[i].first != v[i - 1].first)
			++ct;
		a[v[i].second] = ct;
	}
	// for(auto k : a) cout << k << ' ';
    // cout << endl;
	long long pre[N], suf[N];
	for(int i = 0; i < n; ++i){
		int x = get(a[i] - 1);
		upd(a[i], 1);
		// cout << x << ' ';
		pre[i] = x;
	}
	// cout << endl;
	memset(fenwick, 0, sizeof fenwick);
	for(int i = n - 1; i >= 0; --i){
		int x = get(a[i] - 1);
		upd(a[i], 1);
		suf[i] = x;
	}
	long long ans = 0;
	for(int i = 1; i < n - 1; ++i)
		ans += (pre[i] * suf[i]);
	cout << ans << '\n';
}

int main() {
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
    	solve();
	return 0;
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:61:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   61 |     while(t--)
      |     ^~~~~
Mountains.cpp:63:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   63 |  return 0;
      |  ^~~~~~

• 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