제출 #1199328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199328		prideliqueee	Mountains (NOI20_mountains)	C++20	66 / 100	2096 ms	19184 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
int a[300010];
pair<int,int> mm[1200010];
void build(int l,int r,int i)
{
    if(l==r)
    {
        mm[i]={a[l],a[l]};
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,i*2);
    build(mid+1,r,i*2+1);
    mm[i]={min(mm[i*2].f,mm[i*2+1].f),max(mm[i*2].s,mm[i*2+1].s)};
}
int sum;
void query(int l,int r,int i,int ql,int qr,int val)
{
    //cout<<l<<' '<<r<<' '<<mm[i].f<<' '<<mm[i].s<<endl;
    if(qr<l||ql>r)
    return;
    if(ql<=l&&qr>=r)
    {
        if(mm[i].s<val)
        {
            sum+=(r-l+1);
            return;
        }
        else if(mm[i].f>=val)
        return;
    }
    int mid=(l+r)/2;
    query(l,mid,i*2,ql,qr,val);
    query(mid+1,r,i*2+1,ql,qr,val);
}
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    build(1,n,1);
    int cnt=0;
    for(int i=2;i<n;i++)
    {
        int x=1;
        sum=0;
        query(1,n,1,1,i-1,a[i]);
        x*=sum;
        //cout<<i<<' '<<sum<<' ';
        sum=0;
        query(1,n,1,i+1,n,a[i]);
        //cout<<sum<<' '<<endl;
        x*=sum;
        cnt+=x;
    }
    cout<<cnt;
}

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