Submission #209678

#	Time	Username	Problem	Language	Result	Execution time	Memory
209678		maomao90	Mountains (NOI20_mountains)	C++14	100 / 100	760 ms	43128 KiB

Mountains

#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 (stderr)

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]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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