Submission #329609

#	Time	Username	Problem	Language	Result	Execution time	Memory
329609		TLP39	Mountains (NOI20_mountains)	C++14	100 / 100	136 ms	15340 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;


void so(int x,int y, long long int a[300001],int b[300001],int c[300001])
{
    if(x==y)
    {
        b[x]=0;
        c[x]=0;
        return;
    }
    if(y==x+1)
    {
        if(a[x]<a[x+1])
        {
            b[x]=0;
            c[x]=0;
            b[x+1]=1;
            c[x+1]=0;
        }
        else if(a[x]>a[x+1])
        {
            b[x]=0;
            c[x]=0;
            b[x+1]=0;
            c[x+1]=1;
            long long int temp=a[x];
            a[x]=a[x+1];
            a[x+1]=temp;
        }
        else
        {
            b[x]=0;
            c[x]=0;
            b[x+1]=0;
            c[x+1]=0;
        }
        return;
    }
    int ha=(y-x+1)/2;
    so(x,x+ha-1,a,b,c);
    so(x+ha,y,a,b,c);
    long long int a1[y-x+1]={};
    int b1[y-x+1]={};
    int c1[y-x+1]={};
    int p1=x,p11=x;
    int p2=x+ha;
    int p=0;
    while(p1<x+ha || p2<=y)
    {
        if(p1>=x+ha)
        {
            if(a[p2]>a[p1-1])
            {
                p11=x+ha;
            }
            a1[p]=a[p2];
            b1[p]=b[p2]+(p11-x);
            c1[p]=c[p2];
            p++;
            p2++;
        }
        else if(p2>y)
        {
            a1[p]=a[p1];
            b1[p]=b[p1];
            c1[p]=c[p1]+y-x-ha+1;
            p++;
            p1++;
        }
        else if(a[p1]<=a[p2])
        {
            a1[p]=a[p1];
            b1[p]=b[p1];
            c1[p]=c[p1]+(p2-x-ha);
            if(p1>x && a[p1]!=a[p1-1])
            {
                p11=p1;
            }
            p++;
            p1++;
        }
        else
        {
            if(p1>x && a[p2]>a[p1-1])
            {
                p11=p1;
            }
            a1[p]=a[p2];
            b1[p]=b[p2]+(p11-x);
            c1[p]=c[p2];
            p++;
            p2++;
        }
    }
    for(int i=0;i<=y-x;i++)
    {
        a[x+i]=a1[i];
        b[x+i]=b1[i];
        c[x+i]=c1[i];
    }
    return;
}

int main()
{
    int n;
    scanf("%d",&n);
    long long int h[300001]={};
    int bf[300001]={};
    int af[300001]={};
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&h[i]);
    }
    so(0,n-1,h,bf,af);
    long long int ans=0;
    for(int i=0;i<n;i++)
    {
        ans+=(long long)1*bf[i]*af[i];
    }
    printf("%lld",ans);
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Mountains.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |         scanf("%lld",&h[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