結果

問題 No.1525 Meximum Sum
ユーザー vjudge1
提出日時 2025-12-25 20:45:44
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 7,176 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,809 ms
コンパイル使用メモリ 193,936 KB
実行使用メモリ 10,824 KB
最終ジャッジ日時 2025-12-25 20:45:48
合計ジャッジ時間 3,707 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:77:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   77 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
main.cpp:80:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   80 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define QwQ return
#define egg 0;
#define retrun return
#define int long long
#define iny unsigned long long
#define operaotr operator
//  ? ? ?
// ?     ?
//?       ?
//?       ?
//       ?
//     ?
//    ?
//    ?
//
//    ?
constexpr int maxn=1e6+13;
constexpr int maxm=3e3+13;
constexpr int maxl=2e12+13;
constexpr double pi=acos(-1);
constexpr double eps=1e-8;
constexpr int mod=13131;
constexpr int inf=LONG_LONG_MAX>>1;
constexpr double INF=1e12;

int a[maxn];
int n;
int pos__[maxn];
int solve_D(int arr[])
{
    for(int i=1;i<=n;++i)
    {
        pos__[arr[i]]=i;
    }
    int L=n+1;
    int R=0;
    int ans=0;
    int tot=n*(n+1)/2;
    for(int i=0;i<n;++i)
    {
        int cnt=0;
        int p=pos__[i];
        if(L>R)
        {
            int x=p*(n-p+1);
            cnt=tot-x;
        }
        else
        {
            if(p<L)
            {
                cnt=(L-p)*(n-R+1);
            }
            else if(p>R)
            {
                cnt=L*(p-R);
            }
        }
        ans+=cnt*i;
        if(p<L)
        {
            L=p;
        }
        if(p>R)
        {
            R=p;
        }
    }
    ans+=n;
    return ans;
}

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
    }
    printf("%lld\n",solve_D(a));

    /*
    //I often die
    //I often die
    //I often die
    //I often die
    //I often die
    //I often die
    //I often die
    //I often die
    //I always die */
    QwQ egg
}

/*
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void print(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        print(x/10);
    }
    putchar(x%10+'0');
}
int gcd(int a,int b)// ?????
{
    while (b!=0)
    {
        int temp=b;
        b=a%b;
        a=temp;
    }
    return a;
}

bitset<maxn> pop;
//int prime[maxl];
//int u=0;
void re()// ???
{
    pop.set();
    pop[0]=0;
    pop[1]=0;
    for (int i=2; i<=maxn-3; ++i)
    {
        if(pop[i]==1)
        {
            //++u;
            //prime[u]=i;
            for(int z=i*i; z<=maxn-3; z+=i)
            {
                pop[z]=0;
            }
        }
    }
}
int logn [maxn];
void I ()// ??
{
    logn [0]=0;
    logn [1]=0;
    for (int i=2; i<=maxn-5; ++i)
    {
        logn [i]=logn [i/2]+1;
    }
}
string add (string a,string b)// ?????
{
    string result;
    int carry=0;
    int i=a.size ()-1;
    int j=b.size ()-1;
    while (i>=0||j>=0||carry>0)
    {
        int sum=carry;
        if (i>=0)
        {
            sum+=a [i--]-'0';
        }
        if (j>=0)
        {
            sum+=b [j--]-'0';
        }
        carry=sum/10;
        result.push_back ((sum%10)+'0');
    }
    reverse (result.begin (),result.end ());
    return result;
}
string mul(string a, string b)// ?????
{
    if(a=="0"||b=="0")
    {
        return "0";
    }
    int lenA=a.size();
    int lenB=b.size();
    vector<int> result(lenA+lenB,0);
    for(int i=lenA-1;i>=0;--i)
    {
        int digitA=a[i]-'0';
        for (int j=lenB-1;j>=0;--j)
        {
            int digitB=b[j]-'0';
            int product=digitA*digitB;
            int posLow=i+j+1;
            int posHigh=i+j;
            int sum=product+result[posLow];
            result[posLow]=sum%10;
            result[posHigh]+=sum/10;
        }
    }
    string resStr;
    for(int num:result)
    {
        if (!(resStr.empty()&&num==0))
        {
            resStr.push_back(num+'0');
        }
    }
    return resStr;
}
string sub(string a, string b)//?????
{
    string result;
    int borrow=0;
    int i=a.size()-1;
    int j=b.size()-1;
    while(i>=0||j>=0)
    {
        int digitA=(i>=0)?(a[i--]-'0'):0;
        digitA-=borrow;
        int digitB=(j>=0)?(b[j--]-'0'):0;
        if(digitA<digitB)
        {
            digitA+=10;
            borrow=1;
        }
        else
        {
            borrow=0;
        }
        result.push_back((digitA-digitB)+'0');
    }
    while(result.size()>1&&result.back()=='0')
    {
        result.pop_back();
    }
    reverse(result.begin(), result.end());
    return result;
}
string div(string a, int b) // ?????????????????????????
{
    string result;
    long long current=0;
    bool leadingZero=true;
    if(a=="0")
    {
        return "0";
    }
    int al=a.size();
    for(int i=0;i<al;++i)
    {
        current=current*10+(a[i]-'0');
        int q=current/b;
        current=current%b;
        if(q!=0||!leadingZero)
        {
            result.push_back(q+'0');
            leadingZero=false;
        }
    }
    if (result.empty())
    {
        return "0";
    }
    return result;
}
int ST [maxl][35];
void reason ()// ???? ST ?
{
    int k=logn[n]+1;
    for (int j=1; j<k; ++j)
    {
        for (int i=1; i+(1<<j)-1<=n; ++i)
        {
            ST [i][j]=ST [i][j-1]+ST [i+(1<<(j-1))][j-1];
        }
    }
}
int findnumber (int l,int r)// ????
{
    int sum=0;
    int len=r-l+1;
    while (len>0)
    {
        int k=logn [len];
        sum+=ST [l][k];
        l+=(1<<k);
        len-=(1<<k);
    }
    return sum;
}

int max_prime [maxn];
vector<int> primes;
void BiG ()// ???????????
{
    max_prime [0]=max_prime [1]=0;
    for (int i=2; i<=maxn-5; ++i)
    {
        if (pop[i]==1)
        {
            max_prime [i]=i;
            primes.push_back (i);
        }
        for (int p:primes)
        {
            if (i*p>=maxn-5)
            {
                break;
            }
            if(i%p==0)
            {
                max_prime[i*p]=max_prime[i];
                break;
            }
            else
            {
                max_prime[i*p]=max(max_prime[i],p);
            }
        }
    }
}

int qpow(int a,int b,int p)
{
    int cnt=1;
    a%=p;
    while(b)
    {
        if(b&1)
        {
            cnt*=a;
            cnt%=p;
        }
        a*=a;
        a%=p;
        b>>=1;
    }
    return cnt;
}


int fact [maxn];// ??
int inv_fact [maxn];// ???
void preprocess (int p)// ????? / ??? (?????)
{
    fact[0]=1;
    for (int i=1; i<maxn; ++i)
    {
        fact[i]=fact[i-1]*i%p;
    }
    inv_fact[maxn-1]=qpow(fact[maxn-1],p-2,p);
    for(int i=maxn-2; i>=0; --i)
    {
        inv_fact[i]=inv_fact[i+1]*(i+1)% p;
    }
}

int catalan (int n,int p)// ??????
{
    if (n==0)
    {
        return 1;
    }
    int C=fact[2*n]*inv_fact[n]%p;
    C=C*inv_fact[n]%p;
    int inv =qpow(n+1,p-2,p);
    return C*inv%p;
}

int exgcd(int a, int b, int &x, int &y) //????????????????
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    int Gcd=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return Gcd;
}//??????return qpow(a,p-2,p);

int inverse(int a, int p) //????
{
    int x,y;
    int Gcd=exgcd(a, p, x, y);
    return Gcd==1?(x%p+p)%p:-1;
}

int inv[maxn];
void compute_inv(int n, int p) //?????
{
    inv[1]=1;
    for(int i=2; i<=n; ++i)
    {
        inv[i]=(p-p/i)*inv[p%i]%p;
    }
}
*/
0