Submission #570248

#	Time	Username	Problem	Language	Result	Execution time	Memory
570248		elpro123	Mountains (NOI20_mountains)	C++14	100 / 100	670 ms	40268 KiB

Mountains

#include<bits/stdc++.h>

using namespace std;

struct nodo{
	int s, e, m, cnt;
	nodo *l, *r;
        nodo(int s1, int e1){
        s=s1, e=e1, m=(s1+e1)/2, cnt=0;
		if(s == e) return;
		l = new nodo(s, m);
		r = new nodo(m+1, e);
	}
	void update(int x, int v){
		cnt += v;
		if(s == e) return;
		if(x <= m) l->update(x, v);
		else r->update(x, v);
	}
	int query(int x, int y){
		if(x <= s && y >= e) return cnt;
		int ret = 0;
		if(x <= m) ret += l->query(x, y);
		if(y >= m+1) ret += r->query(x, y);
		return ret;
	}
	void clear(){
		cnt = 0;
		if(s == e) return;
		l->clear();
		r->clear();
	}
};

 
int main(){
    long n; 
    cin>>n;
	long long H[n+1];
	for(int i=1; i<=n; i++){ 
        cin>>H[i];
    }

    long long izquierda[n+1], derecha[n+1];
    pair<long long, int> arreglo[n+1];
    int cnt = 1;
    long long total = 0;

    for(int i=1; i<=n; i++){ 
        arreglo[i] = {H[i], i};
    }
	sort(arreglo + 1, arreglo + n + 1);
 
	for(int i=1; i<=n; i++){
		if(i>1 and arreglo[i].first != arreglo[i-1].first){
            cnt++;
        }
		H[arreglo[i].second] = cnt;
	}
	
	nodo *algo = new nodo(0, n);
	for(int i=1; i<=n; i++){
		izquierda[i] = algo->query(0, H[i] - 1);
		algo->update(H[i], 1);
	}
	
	algo->clear();
	for(int i=n; i>0; i--){
		derecha[i] = algo->query(0, H[i] - 1);
		algo->update(H[i], 1);
	}
	
	for(int i=1; i<=n; i++){
		total += izquierda[i] * derecha[i];
	}

	cout<<total;
	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