#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
int tree[300001], h[300001];
int n;
int sum(int ind)
{
int zbir = 0;
while (ind > 0)
{
zbir += tree[ind];
ind = (ind)&(ind-1);
}
return zbir;
}
void update(int ind)
{
while (ind <= n)
{
tree[ind]++;
ind += (ind & (-ind));
}
}
int query(int left, int right)
{
return (sum(right) - sum(left - 1));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long brojac = 0;
memset(tree, 0, sizeof(tree));
vector <int> reset;
vector <pair<int, int>> order;
cin>>n;
for (int i=1; i<=n; i++)
{
cin>>h[i];
order.pb({h[i], i});
}
sort(order.begin(), order.end());
int last = -1;
for (int i=0; i<order.size(); i++)
{
if (order[i].fr != last)
{
for (int el : reset)
{
update(el);
}
reset.clear();
}
brojac += ((long long)(query(1, order[i].sc-1)))*((long long)query(order[i].sc+1, n));
reset.pb(order[i].sc);
last = order[i].fr;
}
cout<<brojac;
}
Compilation message
Mountains.cpp: In function 'int main()':
Mountains.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i=0; i<order.size(); i++)
| ~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1500 KB |
Output is correct |
2 |
Correct |
39 ms |
7020 KB |
Output is correct |
3 |
Correct |
36 ms |
7104 KB |
Output is correct |
4 |
Correct |
37 ms |
7084 KB |
Output is correct |
5 |
Correct |
37 ms |
7084 KB |
Output is correct |
6 |
Correct |
35 ms |
7072 KB |
Output is correct |
7 |
Correct |
32 ms |
7120 KB |
Output is correct |
8 |
Correct |
31 ms |
7132 KB |
Output is correct |
9 |
Correct |
33 ms |
7088 KB |
Output is correct |
10 |
Correct |
33 ms |
7116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
7340 KB |
Output is correct |
2 |
Correct |
62 ms |
7352 KB |
Output is correct |
3 |
Correct |
61 ms |
7252 KB |
Output is correct |
4 |
Correct |
56 ms |
7236 KB |
Output is correct |
5 |
Correct |
60 ms |
7372 KB |
Output is correct |
6 |
Correct |
60 ms |
7340 KB |
Output is correct |
7 |
Correct |
53 ms |
7372 KB |
Output is correct |
8 |
Correct |
43 ms |
7348 KB |
Output is correct |
9 |
Correct |
61 ms |
7308 KB |
Output is correct |
10 |
Correct |
1 ms |
1492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
7340 KB |
Output is correct |
2 |
Correct |
62 ms |
7352 KB |
Output is correct |
3 |
Correct |
61 ms |
7252 KB |
Output is correct |
4 |
Correct |
56 ms |
7236 KB |
Output is correct |
5 |
Correct |
60 ms |
7372 KB |
Output is correct |
6 |
Correct |
60 ms |
7340 KB |
Output is correct |
7 |
Correct |
53 ms |
7372 KB |
Output is correct |
8 |
Correct |
43 ms |
7348 KB |
Output is correct |
9 |
Correct |
61 ms |
7308 KB |
Output is correct |
10 |
Correct |
1 ms |
1492 KB |
Output is correct |
11 |
Correct |
70 ms |
7280 KB |
Output is correct |
12 |
Correct |
73 ms |
7324 KB |
Output is correct |
13 |
Correct |
68 ms |
7344 KB |
Output is correct |
14 |
Correct |
74 ms |
7328 KB |
Output is correct |
15 |
Correct |
73 ms |
7364 KB |
Output is correct |
16 |
Correct |
72 ms |
7344 KB |
Output is correct |
17 |
Correct |
66 ms |
7224 KB |
Output is correct |
18 |
Correct |
45 ms |
7372 KB |
Output is correct |
19 |
Correct |
46 ms |
7256 KB |
Output is correct |
20 |
Correct |
1 ms |
1508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
7340 KB |
Output is correct |
2 |
Correct |
62 ms |
7352 KB |
Output is correct |
3 |
Correct |
61 ms |
7252 KB |
Output is correct |
4 |
Correct |
56 ms |
7236 KB |
Output is correct |
5 |
Correct |
60 ms |
7372 KB |
Output is correct |
6 |
Correct |
60 ms |
7340 KB |
Output is correct |
7 |
Correct |
53 ms |
7372 KB |
Output is correct |
8 |
Correct |
43 ms |
7348 KB |
Output is correct |
9 |
Correct |
61 ms |
7308 KB |
Output is correct |
10 |
Correct |
1 ms |
1492 KB |
Output is correct |
11 |
Correct |
70 ms |
7280 KB |
Output is correct |
12 |
Correct |
73 ms |
7324 KB |
Output is correct |
13 |
Correct |
68 ms |
7344 KB |
Output is correct |
14 |
Correct |
74 ms |
7328 KB |
Output is correct |
15 |
Correct |
73 ms |
7364 KB |
Output is correct |
16 |
Correct |
72 ms |
7344 KB |
Output is correct |
17 |
Correct |
66 ms |
7224 KB |
Output is correct |
18 |
Correct |
45 ms |
7372 KB |
Output is correct |
19 |
Correct |
46 ms |
7256 KB |
Output is correct |
20 |
Correct |
1 ms |
1508 KB |
Output is correct |
21 |
Correct |
93 ms |
7244 KB |
Output is correct |
22 |
Correct |
83 ms |
7416 KB |
Output is correct |
23 |
Correct |
83 ms |
7272 KB |
Output is correct |
24 |
Correct |
77 ms |
7320 KB |
Output is correct |
25 |
Correct |
87 ms |
7332 KB |
Output is correct |
26 |
Correct |
88 ms |
7260 KB |
Output is correct |
27 |
Correct |
77 ms |
7328 KB |
Output is correct |
28 |
Correct |
49 ms |
7244 KB |
Output is correct |
29 |
Correct |
48 ms |
7364 KB |
Output is correct |
30 |
Correct |
1 ms |
1492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1500 KB |
Output is correct |
2 |
Correct |
39 ms |
7020 KB |
Output is correct |
3 |
Correct |
36 ms |
7104 KB |
Output is correct |
4 |
Correct |
37 ms |
7084 KB |
Output is correct |
5 |
Correct |
37 ms |
7084 KB |
Output is correct |
6 |
Correct |
35 ms |
7072 KB |
Output is correct |
7 |
Correct |
32 ms |
7120 KB |
Output is correct |
8 |
Correct |
31 ms |
7132 KB |
Output is correct |
9 |
Correct |
33 ms |
7088 KB |
Output is correct |
10 |
Correct |
33 ms |
7116 KB |
Output is correct |
11 |
Correct |
60 ms |
7340 KB |
Output is correct |
12 |
Correct |
62 ms |
7352 KB |
Output is correct |
13 |
Correct |
61 ms |
7252 KB |
Output is correct |
14 |
Correct |
56 ms |
7236 KB |
Output is correct |
15 |
Correct |
60 ms |
7372 KB |
Output is correct |
16 |
Correct |
60 ms |
7340 KB |
Output is correct |
17 |
Correct |
53 ms |
7372 KB |
Output is correct |
18 |
Correct |
43 ms |
7348 KB |
Output is correct |
19 |
Correct |
61 ms |
7308 KB |
Output is correct |
20 |
Correct |
1 ms |
1492 KB |
Output is correct |
21 |
Correct |
70 ms |
7280 KB |
Output is correct |
22 |
Correct |
73 ms |
7324 KB |
Output is correct |
23 |
Correct |
68 ms |
7344 KB |
Output is correct |
24 |
Correct |
74 ms |
7328 KB |
Output is correct |
25 |
Correct |
73 ms |
7364 KB |
Output is correct |
26 |
Correct |
72 ms |
7344 KB |
Output is correct |
27 |
Correct |
66 ms |
7224 KB |
Output is correct |
28 |
Correct |
45 ms |
7372 KB |
Output is correct |
29 |
Correct |
46 ms |
7256 KB |
Output is correct |
30 |
Correct |
1 ms |
1508 KB |
Output is correct |
31 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |