#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector <char> vc;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef pair<ll,ll> pl;
typedef double dou;
typedef vector<pl> vpl;
typedef unsigned long long ull;
typedef uint64_t i64;
typedef vector<ull> vull;
#define f first
#define s second
#define pb push_back
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define ts to_string
#define lb lower_bound
#define ub upper_bound
#define yes cout<<'Y'<<'E'<<'S'<<endl
#define no cout<<'N'<<'O'<<endl
#define nd "\n"
void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll mcm(ll a, ll b) {return (a * b) / gcd(a, b);}
bool prime(ll n) {for(int i=2; i<=sqrt(n); i++) if(n%i==0) return false; return true;}
struct compii{bool operator()(const ii &a, const ii &b){if(a.f==a.s)return a.s<b.s;return a.f>b.f;}};
bool comp(int a, int b) {return a>b;}
ll binpow(ll n, ll x){ll ans=1; while(x){if(x&1){ans*=n;}n*=n; x>>=1;} return ans;}
namespace operators {
template<typename T1, typename T2>istream& operator>>(istream& in, pair<T1, T2>& x){in >> x.first >> x.second;return in;}
template<typename T1, typename T2>ostream& operator<<(ostream& out, pair<T1, T2> x){out << x.first << " " << x.second;return out;}
template<typename T1>istream& operator>>(istream& in, vector<T1>& x) {for (auto& i : x) in >> i;return in;}
template<typename T1>ostream& operator<<(ostream& out, vector<T1>& x) {for (auto& i : x) out << i << " ";return out;}
template<typename T1, typename T2>ostream& operator<<(ostream& out, vector<pair <T1,T2>>& x) {for (auto& i : x) out << i.f << " "<<i.s;return out;}
template<typename T1, typename T2>istream& operator>>(istream& in, vector<pair <T1,T2>>& x) {for (auto& i : x) in >> i.f >>i.s;return in;}
}
using namespace operators;
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};
const int pmod = 998244353;
const int mod = 1e9+7;
const ll inf=1e18;
ll sum(ll a, ll b){
return (( (a+mod) %mod) + ((b+mod)%mod))%mod;
}
ll multi(ll a, ll b){
return (((a+mod) %mod) * ((b+mod)%mod))%mod;
}
///
struct FT{
vector<ll> ft;
ll n;
FT(ll m){
n = m;
ft.assign(n+1, 0);
}
ll lsb(ll i){
return (i)&(-i);
}
void add(ll i, ll k){
while(i <= n){
ft[i]+= k;
i+= lsb(i);
}
}
ll get(ll r){
ll res = 0;
while(r){
res+= ft[r];
r-= lsb(r);
}
return res;
}
ll range(ll i, ll j){
if(i == 0) return get(j);
return get(j) - get(i-1);
}
};
void solve(){
ll n;
cin >> n;
vector<ll> a(n, 0), b;
for(ll i = 0; i < n; i++){
cin >> a[i];
}
b = a;
sort(all(b));
map<ll,ll> compress;
ll next = 1;
for(auto v: b){
if(!compress[v]){
compress[v] = next++;
}
}
for(ll i = 0; i < n; i++){
a[i] = compress[a[i]];
}
FT left(n), right(n);
ll l[n], r[n];
for(ll i = 0; i < n; i++){
l[i] = left.range(1, a[i]-1);
left.add(a[i], 1);
}
for(ll i = n-1; i >= 0; i--){
r[i] = right.range(1, a[i]-1);
right.add(a[i], 1);
}
ll res = 0;
for(ll i = 0; i < n; i++){
res+= l[i]*r[i];
}
cout << res << endl;
}
int main (){
setIO("");
int t=1;
//cin >> t;
while(t-->0) solve();
return 0;
}
Compilation message
Mountains.cpp: In function 'void setIO(std::string)':
Mountains.cpp:34:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mountains.cpp:34:128: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
236 ms |
33180 KB |
Output is correct |
3 |
Correct |
225 ms |
33140 KB |
Output is correct |
4 |
Correct |
210 ms |
33180 KB |
Output is correct |
5 |
Correct |
215 ms |
33244 KB |
Output is correct |
6 |
Correct |
213 ms |
33140 KB |
Output is correct |
7 |
Correct |
201 ms |
33168 KB |
Output is correct |
8 |
Correct |
218 ms |
33100 KB |
Output is correct |
9 |
Correct |
168 ms |
24020 KB |
Output is correct |
10 |
Correct |
170 ms |
24144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
74 ms |
14308 KB |
Output is correct |
2 |
Correct |
76 ms |
14324 KB |
Output is correct |
3 |
Correct |
59 ms |
14388 KB |
Output is correct |
4 |
Correct |
64 ms |
14364 KB |
Output is correct |
5 |
Correct |
72 ms |
14400 KB |
Output is correct |
6 |
Correct |
72 ms |
14284 KB |
Output is correct |
7 |
Correct |
66 ms |
14392 KB |
Output is correct |
8 |
Correct |
54 ms |
14392 KB |
Output is correct |
9 |
Correct |
57 ms |
14396 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
74 ms |
14308 KB |
Output is correct |
2 |
Correct |
76 ms |
14324 KB |
Output is correct |
3 |
Correct |
59 ms |
14388 KB |
Output is correct |
4 |
Correct |
64 ms |
14364 KB |
Output is correct |
5 |
Correct |
72 ms |
14400 KB |
Output is correct |
6 |
Correct |
72 ms |
14284 KB |
Output is correct |
7 |
Correct |
66 ms |
14392 KB |
Output is correct |
8 |
Correct |
54 ms |
14392 KB |
Output is correct |
9 |
Correct |
57 ms |
14396 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
79 ms |
14360 KB |
Output is correct |
12 |
Correct |
87 ms |
14364 KB |
Output is correct |
13 |
Correct |
77 ms |
14372 KB |
Output is correct |
14 |
Correct |
77 ms |
14360 KB |
Output is correct |
15 |
Correct |
72 ms |
14448 KB |
Output is correct |
16 |
Correct |
74 ms |
14448 KB |
Output is correct |
17 |
Correct |
81 ms |
14492 KB |
Output is correct |
18 |
Correct |
65 ms |
14400 KB |
Output is correct |
19 |
Correct |
57 ms |
14404 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
356 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
356 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
7 ms |
1364 KB |
Output is correct |
12 |
Correct |
8 ms |
1344 KB |
Output is correct |
13 |
Correct |
7 ms |
1364 KB |
Output is correct |
14 |
Correct |
7 ms |
1364 KB |
Output is correct |
15 |
Correct |
8 ms |
1364 KB |
Output is correct |
16 |
Correct |
8 ms |
1296 KB |
Output is correct |
17 |
Correct |
7 ms |
1364 KB |
Output is correct |
18 |
Correct |
7 ms |
980 KB |
Output is correct |
19 |
Correct |
3 ms |
724 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
74 ms |
14308 KB |
Output is correct |
2 |
Correct |
76 ms |
14324 KB |
Output is correct |
3 |
Correct |
59 ms |
14388 KB |
Output is correct |
4 |
Correct |
64 ms |
14364 KB |
Output is correct |
5 |
Correct |
72 ms |
14400 KB |
Output is correct |
6 |
Correct |
72 ms |
14284 KB |
Output is correct |
7 |
Correct |
66 ms |
14392 KB |
Output is correct |
8 |
Correct |
54 ms |
14392 KB |
Output is correct |
9 |
Correct |
57 ms |
14396 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
79 ms |
14360 KB |
Output is correct |
12 |
Correct |
87 ms |
14364 KB |
Output is correct |
13 |
Correct |
77 ms |
14372 KB |
Output is correct |
14 |
Correct |
77 ms |
14360 KB |
Output is correct |
15 |
Correct |
72 ms |
14448 KB |
Output is correct |
16 |
Correct |
74 ms |
14448 KB |
Output is correct |
17 |
Correct |
81 ms |
14492 KB |
Output is correct |
18 |
Correct |
65 ms |
14400 KB |
Output is correct |
19 |
Correct |
57 ms |
14404 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
251 ms |
20348 KB |
Output is correct |
22 |
Correct |
236 ms |
20332 KB |
Output is correct |
23 |
Correct |
258 ms |
20236 KB |
Output is correct |
24 |
Correct |
253 ms |
20300 KB |
Output is correct |
25 |
Correct |
238 ms |
20340 KB |
Output is correct |
26 |
Correct |
262 ms |
20304 KB |
Output is correct |
27 |
Correct |
216 ms |
20248 KB |
Output is correct |
28 |
Correct |
129 ms |
20300 KB |
Output is correct |
29 |
Correct |
147 ms |
20336 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
236 ms |
33180 KB |
Output is correct |
3 |
Correct |
225 ms |
33140 KB |
Output is correct |
4 |
Correct |
210 ms |
33180 KB |
Output is correct |
5 |
Correct |
215 ms |
33244 KB |
Output is correct |
6 |
Correct |
213 ms |
33140 KB |
Output is correct |
7 |
Correct |
201 ms |
33168 KB |
Output is correct |
8 |
Correct |
218 ms |
33100 KB |
Output is correct |
9 |
Correct |
168 ms |
24020 KB |
Output is correct |
10 |
Correct |
170 ms |
24144 KB |
Output is correct |
11 |
Correct |
74 ms |
14308 KB |
Output is correct |
12 |
Correct |
76 ms |
14324 KB |
Output is correct |
13 |
Correct |
59 ms |
14388 KB |
Output is correct |
14 |
Correct |
64 ms |
14364 KB |
Output is correct |
15 |
Correct |
72 ms |
14400 KB |
Output is correct |
16 |
Correct |
72 ms |
14284 KB |
Output is correct |
17 |
Correct |
66 ms |
14392 KB |
Output is correct |
18 |
Correct |
54 ms |
14392 KB |
Output is correct |
19 |
Correct |
57 ms |
14396 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
79 ms |
14360 KB |
Output is correct |
22 |
Correct |
87 ms |
14364 KB |
Output is correct |
23 |
Correct |
77 ms |
14372 KB |
Output is correct |
24 |
Correct |
77 ms |
14360 KB |
Output is correct |
25 |
Correct |
72 ms |
14448 KB |
Output is correct |
26 |
Correct |
74 ms |
14448 KB |
Output is correct |
27 |
Correct |
81 ms |
14492 KB |
Output is correct |
28 |
Correct |
65 ms |
14400 KB |
Output is correct |
29 |
Correct |
57 ms |
14404 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
356 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
41 |
Correct |
7 ms |
1364 KB |
Output is correct |
42 |
Correct |
8 ms |
1344 KB |
Output is correct |
43 |
Correct |
7 ms |
1364 KB |
Output is correct |
44 |
Correct |
7 ms |
1364 KB |
Output is correct |
45 |
Correct |
8 ms |
1364 KB |
Output is correct |
46 |
Correct |
8 ms |
1296 KB |
Output is correct |
47 |
Correct |
7 ms |
1364 KB |
Output is correct |
48 |
Correct |
7 ms |
980 KB |
Output is correct |
49 |
Correct |
3 ms |
724 KB |
Output is correct |
50 |
Correct |
0 ms |
212 KB |
Output is correct |
51 |
Correct |
251 ms |
20348 KB |
Output is correct |
52 |
Correct |
236 ms |
20332 KB |
Output is correct |
53 |
Correct |
258 ms |
20236 KB |
Output is correct |
54 |
Correct |
253 ms |
20300 KB |
Output is correct |
55 |
Correct |
238 ms |
20340 KB |
Output is correct |
56 |
Correct |
262 ms |
20304 KB |
Output is correct |
57 |
Correct |
216 ms |
20248 KB |
Output is correct |
58 |
Correct |
129 ms |
20300 KB |
Output is correct |
59 |
Correct |
147 ms |
20336 KB |
Output is correct |
60 |
Correct |
0 ms |
212 KB |
Output is correct |
61 |
Correct |
469 ms |
33140 KB |
Output is correct |
62 |
Correct |
442 ms |
33148 KB |
Output is correct |
63 |
Correct |
444 ms |
33184 KB |
Output is correct |
64 |
Correct |
434 ms |
33148 KB |
Output is correct |
65 |
Correct |
438 ms |
33140 KB |
Output is correct |
66 |
Correct |
431 ms |
33140 KB |
Output is correct |
67 |
Correct |
431 ms |
33180 KB |
Output is correct |
68 |
Correct |
348 ms |
24084 KB |
Output is correct |
69 |
Correct |
264 ms |
22512 KB |
Output is correct |
70 |
Correct |
0 ms |
212 KB |
Output is correct |