# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
583507 | Kanaifu | Mountains (NOI20_mountains) | C++17 | 94 ms | 9868 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
int tree[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));
}
}
long long 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<long long, int>> order;
cin>>n;
for (int i=1; i<=n; i++)
{
long long height;
cin>>height;
order.pb({height, 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 += (query(1, order[i].sc-1))*(query(order[i].sc+1, n));
reset.pb(order[i].sc);
last = order[i].fr;
}
cout<<brojac;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |