Submission #585377

#	Time	Username	Problem	Language	Result	Execution time	Memory
585377		Kanaifu	Mountains (NOI20_mountains)	C++14	100 / 100	123 ms	14924 KiB

Mountains

#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 & (ind-1)));
    }
}

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());
    long long 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)

Mountains.cpp: In function 'int main()':
Mountains.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i=0; i<order.size(); i++)
      |                   ~^~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 9 / 9
• Subtask 7: 12 / 12