Submission #830141

#	Time	Username	Problem	Language	Result	Execution time	Memory
830141		NK_	Mountains (NOI20_mountains)	C++17	100 / 100	374 ms	27072 KiB

Mountains

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;
 
#define nl '\n'
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;
using db = long double;

const int INF = 1e9 + 10;


struct BIT {
	int N; vl A; void init(int n) { N = n; A = vl(N, 0); }
	void upd(int p, int x) { for(++p;p<=N;p+=p&-p) A[p-1] += x; }
	ll sum(int l, int r) { return sum(r + 1) - sum(l); }
	ll sum(int r) { ll s = 0; for(;r;r-=r&-r) s += A[r-1]; return s; }
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	vl A(N); for(auto& x : A) cin >> x;

	int M = -1;
	{
		map<ll, int> C; int cur = 0;
		for(auto& x : A) C[x]++;
		for(auto& x : C) x.s = cur++;
		for(auto& x : A) x = C[x];
		M = cur;
	}

	BIT up, dwn; up.init(M); dwn.init(M);
	ll ans = 0;
	for(auto& x : A) {
		ans += dwn.sum(x + 1, M - 1);
		ll DWN = up.sum(0, x - 1);
		dwn.upd(x, DWN);
		up.upd(x, 1);
	}
	cout << ans << nl;
    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