Submission #933635

#	Time	Username	Problem	Language	Result	Execution time	Memory
933635		Spazmash	Mountains (NOI20_mountains)	C++17	100 / 100	916 ms	76468 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ld long double
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define elif else if
#define x first
#define y second
ll n, a[300001], tree[1300001], ans;
vector<ll> del[300001], vec;
map<ll, bool> vis;
map<ll, ll> eval;

ll query(ll tidx, ll tl, ll tr, ll l, ll r){
	if(l>tr)return 0;
	if(r<tl)return 0;
	if(l<=tl && r>=tr)return tree[tidx];
	ll tmid=(tl+tr)/2;
	return query(tidx*2, tl, tmid, l, r)+query(tidx*2+1, tmid+1, tr, l, r);
}

void update(ll tidx, ll tl, ll tr, ll idx){
	if(tl==tr && tl==idx){
		tree[tidx]=0;
		return;
	}
	if(tl>idx)return;
	if(tr<idx)return;
	ll tmid=(tl+tr)/2;
	update(tidx*2, tl, tmid, idx);
	update(tidx*2+1, tmid+1, tr, idx);
	tree[tidx]=tree[tidx*2]+tree[tidx*2+1];
}

void build(ll tidx, ll tl, ll tr){
	if(tl==tr){
		tree[tidx]=1;
		return ;
	}
	ll tmid=(tl+tr)/2;
	build(tidx*2, tl, tmid);
	build(tidx*2+1, tmid+1, tr);
	tree[tidx]=tree[tidx*2]+tree[tidx*2+1];
}

int main() {
	cin >> n;
	for(int i=1; i<=n; i++){
		cin >> a[i];
		if(!vis[a[i]])vec.pb(a[i]);
		vis[a[i]]=true;
	}
	sort(vec.begin(), vec.end());
	for(int i=0; i<vec.size(); i++){
		eval[vec[i]]=i+1;
	}
	for(int i=1; i<=n; i++){
		a[i]=eval[a[i]];
		del[a[i]].pb(i);
	}
	build(1, 1, n);
	for(int i=vec.size(); i>=1; i--){
		for(auto j:del[i]){
			update(1, 1, n, j);
		}
		for(auto j:del[i]){
			ans+=query(1, 1, n, 1, j-1)*query(1, 1, n, j+1, n);
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i=0; i<vec.size(); i++){
      |               ~^~~~~~~~~~~

• 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