#include <cstdio>
#include <set>
#include <utility>
#include <map>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<long long, int> li;
//#define DEBUG
/*
int n;
long long mountain[300005];
multiset <li> lower, upper;
long long ans;
int main1(), main2();
int main()
{
scanf("%d", &n);
if (n <= 10000) main1();
else main2();
}
int main1()
{
for (int i = 0; i < n; i++)
{
scanf("%lld", &mountain[i]);
if (i == 0) lower.insert(li(mountain[i], i));
else if (i > 1) upper.insert(li(mountain[i], i));
}
for (int i = 1; i < n - 1; i++)
{
#ifdef DEBUG
printf("Lower:");
for (auto &it : lower)
{
printf(" (%d, %d)", it.first, it.second);
}
printf("\nUpper:");
for (auto &it : upper)
{
printf(" (%d, %d)", it.first, it.second);
}
printf("\n");
#endif // DEBUG
multiset <li> :: iterator lowerbound = lower.lower_bound(li(mountain[i], -1));
multiset <li> :: iterator upperbound = upper.lower_bound(li(mountain[i], -1));
long long numLower = distance(lower.begin(), lowerbound);
long long numUpper = distance(upper.begin(), upperbound);
#ifdef DEBUG
printf("numLower: %d; numUpper: %d\n\n", numLower, numUpper);
#endif // DEBUG
ans += numLower * numUpper;
lower.insert(li(mountain[i], i));
upper.erase(li(mountain[i + 1], i + 1));
}
printf("%lld\n", ans);
return 0;
}
*/
int n;
long long mountain[300005];
set <long long> sorted;
int newMountain[300005];
map <long long, int> key;
int lower[300005], upper[300005];
long long res;
int fenwick[1000005];
void update(int a, long long v)
{
while (a < n + 5)
{
fenwick[a] += v;
a += a & (-a);
}
}
int query(int a)
{
int ans = 0;
while (a > 0)
{
ans += fenwick[a];
a -= a & (-a);
}
return ans;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%lld", &mountain[i]);
sorted.insert(mountain[i]);
}
int counter = 1;
for (auto &it : sorted) key[it] = counter++;
for (int i = 0; i < n; i++) newMountain[i] = key[mountain[i]];
#ifdef DEBUG
printf("newMountain:");
for (int i = 0; i < n; i++) printf(" %d", newMountain[i]);
printf("\n");
#endif // DEBUG
for (int i = 1; i < n - 1; i++)
{
update(newMountain[i - 1], 1); lower[i] = query(newMountain[i] - 1);
}
memset(fenwick, 0, sizeof(fenwick));
for (int i = n - 2; i > 0; i--)
{
update(newMountain[i + 1], 1); upper[i] = query(newMountain[i] - 1);
}
for (int i = 1; i < n - 1; i++)
{
res += (long long) lower[i] * upper[i];
}
printf("%lld\n", res);
return 0;
}
/*
5
0 1 1 0 1
*/
Compilation message
Mountains.cpp: In function 'int main()':
Mountains.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
Mountains.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &mountain[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4212 KB |
Output is correct |
2 |
Correct |
300 ms |
43128 KB |
Output is correct |
3 |
Correct |
302 ms |
43000 KB |
Output is correct |
4 |
Correct |
308 ms |
42916 KB |
Output is correct |
5 |
Correct |
301 ms |
43000 KB |
Output is correct |
6 |
Correct |
311 ms |
42976 KB |
Output is correct |
7 |
Correct |
308 ms |
43000 KB |
Output is correct |
8 |
Correct |
307 ms |
43000 KB |
Output is correct |
9 |
Correct |
220 ms |
27128 KB |
Output is correct |
10 |
Correct |
217 ms |
27128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
10104 KB |
Output is correct |
2 |
Correct |
84 ms |
10104 KB |
Output is correct |
3 |
Correct |
70 ms |
10104 KB |
Output is correct |
4 |
Correct |
70 ms |
10104 KB |
Output is correct |
5 |
Correct |
68 ms |
10104 KB |
Output is correct |
6 |
Correct |
68 ms |
10104 KB |
Output is correct |
7 |
Correct |
70 ms |
10108 KB |
Output is correct |
8 |
Correct |
71 ms |
10104 KB |
Output is correct |
9 |
Correct |
66 ms |
10104 KB |
Output is correct |
10 |
Correct |
7 ms |
4216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
10104 KB |
Output is correct |
2 |
Correct |
84 ms |
10104 KB |
Output is correct |
3 |
Correct |
70 ms |
10104 KB |
Output is correct |
4 |
Correct |
70 ms |
10104 KB |
Output is correct |
5 |
Correct |
68 ms |
10104 KB |
Output is correct |
6 |
Correct |
68 ms |
10104 KB |
Output is correct |
7 |
Correct |
70 ms |
10108 KB |
Output is correct |
8 |
Correct |
71 ms |
10104 KB |
Output is correct |
9 |
Correct |
66 ms |
10104 KB |
Output is correct |
10 |
Correct |
7 ms |
4216 KB |
Output is correct |
11 |
Correct |
99 ms |
10104 KB |
Output is correct |
12 |
Correct |
94 ms |
10104 KB |
Output is correct |
13 |
Correct |
92 ms |
10104 KB |
Output is correct |
14 |
Correct |
97 ms |
10104 KB |
Output is correct |
15 |
Correct |
99 ms |
10104 KB |
Output is correct |
16 |
Correct |
94 ms |
10104 KB |
Output is correct |
17 |
Correct |
99 ms |
10104 KB |
Output is correct |
18 |
Correct |
69 ms |
10104 KB |
Output is correct |
19 |
Correct |
73 ms |
10104 KB |
Output is correct |
20 |
Correct |
7 ms |
4216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4344 KB |
Output is correct |
2 |
Correct |
7 ms |
4344 KB |
Output is correct |
3 |
Correct |
7 ms |
4344 KB |
Output is correct |
4 |
Correct |
7 ms |
4344 KB |
Output is correct |
5 |
Correct |
7 ms |
4344 KB |
Output is correct |
6 |
Correct |
7 ms |
4348 KB |
Output is correct |
7 |
Correct |
7 ms |
4344 KB |
Output is correct |
8 |
Correct |
7 ms |
4216 KB |
Output is correct |
9 |
Correct |
7 ms |
4216 KB |
Output is correct |
10 |
Correct |
7 ms |
4220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4344 KB |
Output is correct |
2 |
Correct |
7 ms |
4344 KB |
Output is correct |
3 |
Correct |
7 ms |
4344 KB |
Output is correct |
4 |
Correct |
7 ms |
4344 KB |
Output is correct |
5 |
Correct |
7 ms |
4344 KB |
Output is correct |
6 |
Correct |
7 ms |
4348 KB |
Output is correct |
7 |
Correct |
7 ms |
4344 KB |
Output is correct |
8 |
Correct |
7 ms |
4216 KB |
Output is correct |
9 |
Correct |
7 ms |
4216 KB |
Output is correct |
10 |
Correct |
7 ms |
4220 KB |
Output is correct |
11 |
Correct |
17 ms |
5496 KB |
Output is correct |
12 |
Correct |
17 ms |
5496 KB |
Output is correct |
13 |
Correct |
18 ms |
5496 KB |
Output is correct |
14 |
Correct |
16 ms |
5496 KB |
Output is correct |
15 |
Correct |
18 ms |
5496 KB |
Output is correct |
16 |
Correct |
16 ms |
5496 KB |
Output is correct |
17 |
Correct |
16 ms |
5496 KB |
Output is correct |
18 |
Correct |
13 ms |
4856 KB |
Output is correct |
19 |
Correct |
10 ms |
4472 KB |
Output is correct |
20 |
Correct |
7 ms |
4216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
10104 KB |
Output is correct |
2 |
Correct |
84 ms |
10104 KB |
Output is correct |
3 |
Correct |
70 ms |
10104 KB |
Output is correct |
4 |
Correct |
70 ms |
10104 KB |
Output is correct |
5 |
Correct |
68 ms |
10104 KB |
Output is correct |
6 |
Correct |
68 ms |
10104 KB |
Output is correct |
7 |
Correct |
70 ms |
10108 KB |
Output is correct |
8 |
Correct |
71 ms |
10104 KB |
Output is correct |
9 |
Correct |
66 ms |
10104 KB |
Output is correct |
10 |
Correct |
7 ms |
4216 KB |
Output is correct |
11 |
Correct |
99 ms |
10104 KB |
Output is correct |
12 |
Correct |
94 ms |
10104 KB |
Output is correct |
13 |
Correct |
92 ms |
10104 KB |
Output is correct |
14 |
Correct |
97 ms |
10104 KB |
Output is correct |
15 |
Correct |
99 ms |
10104 KB |
Output is correct |
16 |
Correct |
94 ms |
10104 KB |
Output is correct |
17 |
Correct |
99 ms |
10104 KB |
Output is correct |
18 |
Correct |
69 ms |
10104 KB |
Output is correct |
19 |
Correct |
73 ms |
10104 KB |
Output is correct |
20 |
Correct |
7 ms |
4216 KB |
Output is correct |
21 |
Correct |
339 ms |
20472 KB |
Output is correct |
22 |
Correct |
363 ms |
20472 KB |
Output is correct |
23 |
Correct |
369 ms |
20472 KB |
Output is correct |
24 |
Correct |
380 ms |
20472 KB |
Output is correct |
25 |
Correct |
356 ms |
20472 KB |
Output is correct |
26 |
Correct |
330 ms |
20476 KB |
Output is correct |
27 |
Correct |
328 ms |
20472 KB |
Output is correct |
28 |
Correct |
155 ms |
20600 KB |
Output is correct |
29 |
Correct |
163 ms |
20472 KB |
Output is correct |
30 |
Correct |
7 ms |
4216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4212 KB |
Output is correct |
2 |
Correct |
300 ms |
43128 KB |
Output is correct |
3 |
Correct |
302 ms |
43000 KB |
Output is correct |
4 |
Correct |
308 ms |
42916 KB |
Output is correct |
5 |
Correct |
301 ms |
43000 KB |
Output is correct |
6 |
Correct |
311 ms |
42976 KB |
Output is correct |
7 |
Correct |
308 ms |
43000 KB |
Output is correct |
8 |
Correct |
307 ms |
43000 KB |
Output is correct |
9 |
Correct |
220 ms |
27128 KB |
Output is correct |
10 |
Correct |
217 ms |
27128 KB |
Output is correct |
11 |
Correct |
73 ms |
10104 KB |
Output is correct |
12 |
Correct |
84 ms |
10104 KB |
Output is correct |
13 |
Correct |
70 ms |
10104 KB |
Output is correct |
14 |
Correct |
70 ms |
10104 KB |
Output is correct |
15 |
Correct |
68 ms |
10104 KB |
Output is correct |
16 |
Correct |
68 ms |
10104 KB |
Output is correct |
17 |
Correct |
70 ms |
10108 KB |
Output is correct |
18 |
Correct |
71 ms |
10104 KB |
Output is correct |
19 |
Correct |
66 ms |
10104 KB |
Output is correct |
20 |
Correct |
7 ms |
4216 KB |
Output is correct |
21 |
Correct |
99 ms |
10104 KB |
Output is correct |
22 |
Correct |
94 ms |
10104 KB |
Output is correct |
23 |
Correct |
92 ms |
10104 KB |
Output is correct |
24 |
Correct |
97 ms |
10104 KB |
Output is correct |
25 |
Correct |
99 ms |
10104 KB |
Output is correct |
26 |
Correct |
94 ms |
10104 KB |
Output is correct |
27 |
Correct |
99 ms |
10104 KB |
Output is correct |
28 |
Correct |
69 ms |
10104 KB |
Output is correct |
29 |
Correct |
73 ms |
10104 KB |
Output is correct |
30 |
Correct |
7 ms |
4216 KB |
Output is correct |
31 |
Correct |
7 ms |
4344 KB |
Output is correct |
32 |
Correct |
7 ms |
4344 KB |
Output is correct |
33 |
Correct |
7 ms |
4344 KB |
Output is correct |
34 |
Correct |
7 ms |
4344 KB |
Output is correct |
35 |
Correct |
7 ms |
4344 KB |
Output is correct |
36 |
Correct |
7 ms |
4348 KB |
Output is correct |
37 |
Correct |
7 ms |
4344 KB |
Output is correct |
38 |
Correct |
7 ms |
4216 KB |
Output is correct |
39 |
Correct |
7 ms |
4216 KB |
Output is correct |
40 |
Correct |
7 ms |
4220 KB |
Output is correct |
41 |
Correct |
17 ms |
5496 KB |
Output is correct |
42 |
Correct |
17 ms |
5496 KB |
Output is correct |
43 |
Correct |
18 ms |
5496 KB |
Output is correct |
44 |
Correct |
16 ms |
5496 KB |
Output is correct |
45 |
Correct |
18 ms |
5496 KB |
Output is correct |
46 |
Correct |
16 ms |
5496 KB |
Output is correct |
47 |
Correct |
16 ms |
5496 KB |
Output is correct |
48 |
Correct |
13 ms |
4856 KB |
Output is correct |
49 |
Correct |
10 ms |
4472 KB |
Output is correct |
50 |
Correct |
7 ms |
4216 KB |
Output is correct |
51 |
Correct |
339 ms |
20472 KB |
Output is correct |
52 |
Correct |
363 ms |
20472 KB |
Output is correct |
53 |
Correct |
369 ms |
20472 KB |
Output is correct |
54 |
Correct |
380 ms |
20472 KB |
Output is correct |
55 |
Correct |
356 ms |
20472 KB |
Output is correct |
56 |
Correct |
330 ms |
20476 KB |
Output is correct |
57 |
Correct |
328 ms |
20472 KB |
Output is correct |
58 |
Correct |
155 ms |
20600 KB |
Output is correct |
59 |
Correct |
163 ms |
20472 KB |
Output is correct |
60 |
Correct |
7 ms |
4216 KB |
Output is correct |
61 |
Correct |
760 ms |
42976 KB |
Output is correct |
62 |
Correct |
742 ms |
43000 KB |
Output is correct |
63 |
Correct |
746 ms |
43000 KB |
Output is correct |
64 |
Correct |
740 ms |
43000 KB |
Output is correct |
65 |
Correct |
749 ms |
43000 KB |
Output is correct |
66 |
Correct |
736 ms |
42900 KB |
Output is correct |
67 |
Correct |
752 ms |
43008 KB |
Output is correct |
68 |
Correct |
498 ms |
27128 KB |
Output is correct |
69 |
Correct |
409 ms |
24312 KB |
Output is correct |
70 |
Correct |
8 ms |
4344 KB |
Output is correct |