Submission #680201

#TimeUsernameProblemLanguageResultExecution timeMemory
680201abcvuitunggioMountains (NOI20_mountains)C++17
100 / 100
254 ms29364 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cstdio> #define int long long using namespace std; int n,a[300001],res,ft[300001]; vector <int> v,ve[300001]; void update(int i){ for (;i<=n;i+=i&(-i)) ft[i]++; } int get(int i){ int res=0; for (;i;i-=i&(-i)) res+=ft[i]; return res; } int32_t main(){ ios_base::sync_with_stdio(NULL);cin.tie(nullptr); //freopen("xyz.inp","r",stdin); //freopen("xyz.out","w",stdout); cin >> n; for (int i=1;i<=n;i++){ cin >> a[i]; v.push_back(a[i]); } sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end())-v.begin()); for (int i=1;i<=n;i++){ a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1; ve[a[i]].push_back(i); } for (int i=1;i<=n;i++) if (!ve[i].empty()){ for (int j:ve[i]) res+=get(j-1)*(get(n)-get(j)); for (int j:ve[i]) update(j); } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...