Submission #1316368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316368		djsksbrbf	Mountains (NOI20_mountains)	C++20	49 / 100	2096 ms	22104 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
#define fi first
#define se second
#define pb push_back
const int MOD = 1e9;
const int MAX = 2e5 + 5;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
#define int ll

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   
   int n; cin >> n;
   int a[n + 5];
   for(int i = 1 ; i <= n ; i++)cin >> a[i];
   map <int, int> tot;
   for(int i = 1 ; i <= n ; i++)tot[a[i]]++;
   map <int, int> mp;
   
   ll ans = 0;
   for(int i = 1 ; i <= n ; i++){
      int le = 0, ri = 0;
      for(auto it : tot){
         if(it.fi >= a[i])break;
         ri += it.se;
         le += mp[it.fi];
      }
      
      ans += le*ri;
      mp[a[i]]++;
      tot[a[i]]--;
   }
   cout << ans << endl;
   
   return 0;
}

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