UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199152#26. T1xiaopangfeiyu1001983ms38724kbC++116.6kb2023-12-05 10:54:442023-12-05 12:06:42

answer

            /*
                            _/                                        _/                                     
                           _/                                        _/                                                             
                          _/                                        _/                                                         
                         _/                                        _/                      
                        _/            _/                          _/                        
                       _/_/_/_/                        _/        _/_/_/_/                    _/                
          _/_/_/_/    _/      _/    _/    _/ _/_/ _/_/_/_/_/    _/     _/     _/_/_/    _/_/_/_/_/    _/_/_/              
         _/     _/   _/      _/    _/    _/_/        _/        _/      _/   _/    _/       _/       _/     _/
        _/     _/   _/      _/    _/    _/          _/        _/      _/  _/_/_/_/_/      _/       _/     _/          
       _/     _/   _/      _/    _/    _/          _/  _/    _/      _/   _/      _/     _/  _/   _/     _/          
      _/_/_/_/    _/      _/    _/    _/          _/_/_/    _/      _/    _/_/_/_/      _/_/_/    _/_/_/ _/     
     _/
    _/
   _/
  _/
 _/
_/
*/
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include <bits/stdc++.h>

#define MAXN 200005
#define int long long
#define MOD 1000000007

using namespace std;

inline int read()
{
    int x=0;
    char c=getchar();
    while(!isdigit(c)) {c=getchar();}
    while(isdigit(c))  {x=x*10+c-'0',c=getchar();}
    return x;
}

int n,m;
set<int>se;
struct node {int id,x;} a[MAXN];
bool cmp1(node p,node q) {if(p.x!=q.x) {return p.x>q.x;} return p.id<q.id;}
int ans;


int get(int x) {return x*(x+1)/2%MOD;}
struct segtree
{
    int l,r;
    int ls,rs;
    int lum,rum,num,sum;
}t[MAXN*4];
int tot;
void update(int x)
{
    t[x].num=t[t[x].ls].num+t[t[x].rs].num;
    if(t[t[x].ls].num==t[t[x].ls].r-t[t[x].ls].l+1) {t[x].lum=t[t[x].ls].num+t[t[x].rs].lum;}
    else {t[x].lum=t[t[x].ls].lum;}
    if(t[t[x].rs].num==t[t[x].rs].r-t[t[x].rs].l+1) {t[x].rum=t[t[x].rs].num+t[t[x].ls].rum;}
    else {t[x].rum=t[t[x].rs].rum;}
    t[x].sum=(t[t[x].ls].sum+t[t[x].rs].sum-get(t[t[x].ls].rum)-get(t[t[x].rs].lum)+get(t[t[x].ls].rum+t[t[x].rs].lum)+MOD)%MOD;
}
void check(int x)
{
    int mid=(t[x].l+t[x].r)/2;
    if(!t[x].ls) {t[x].ls=++tot;t[tot].l=t[x].l;t[tot].r=mid;}
    if(!t[x].rs) {t[x].rs=++tot;t[tot].r=t[x].r;t[tot].l=mid+1;}
}
void ins(int x,int k)
{
    if(t[x].l==k&&k==t[x].r)
    {
        t[x].num=t[x].lum=t[x].rum=t[x].sum=1;
        return ;
    }
    int mid=(t[x].l+t[x].r)/2;
    check(x);
    if(k<=mid) {ins(t[x].ls,k);}
    else       {ins(t[x].rs,k);}
    update(x);
}
signed main()
{
    int i,j,k;
    n=read();for(i=1;i<=n;i++) {a[i].x=read();a[i].id=i;se.insert(i);}
    se.insert(0),se.insert(n+1);
    sort(a+1,a+n+1,cmp1);
    t[++tot].l=1;t[tot].r=n;
    for(i=1;i<=n;i++)
    {
        ins(1,a[i].id);
        int all=t[1].sum;   
        se.erase(a[i].id);
        int L=0,R=0;
        auto x=se.lower_bound(a[i].id);
        auto y=prev(x);
        L=a[i].id-*y-1;
        R=*x-a[i].id-1;

        int exd=L+R+1;
        exd=(exd+1)*exd/2%MOD;
        int res=0;
        res=(res+(all-exd)*(L+1)%MOD*(R+1)%MOD)%MOD;
        res=(res+R*(R+1)*(R+2)/6%MOD*(L+1)%MOD+L*(L+1)*(L+2)/6%MOD*(R+1)%MOD)%MOD;
        ans=(ans+res*a[i].x%MOD)%MOD;
    }
    cout<<ans;
    return 0;
}
/*
              _/                                             _/                                     
              _/                                             _/                                                             
              _/                                             _/                                                         
              _/                                             _/                      
              _/              _/                             _/                        
              _/ _/_/_/                           _/        _/ _/_/_/                     _/                
_/_/_/_/_/    _/_/     _/    _/    _/ _/_/_/  _/_/_/_/_/    _/_/     _/     _/_/_/    _/_/_/_/_/     _/_/_/              
_/       _/   _/       _/    _/    _/_/           _/        _/       _/    _/    _/       _/        _/     _/
_/       _/   _/       _/    _/    _/             _/        _/       _/   _/_/_/_/_/      _/        _/     _/          
_/       _/   _/       _/    _/    _/             _/  _/    _/       _/    _/      _/     _/  _/    _/     _/          
_/_/_/_/_/    _/       _/    _/    _/             _/_/_/    _/       _/     _/_/_/_/      _/_/_/     _/_/_/ _/     
_/
_/
_/
_/
_/
_/
*/
Source code, Language: C++11

Details

小提示：点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 1ms
memory: 1236kb

input:

50
55892241
441028315
56244117
659101962
534791587
51590963
870682245
964013917
14874241
555206021
2...

output:

634701953

result:

ok 1 number(s): "634701953"

Test #2:

score: 10
Accepted
time: 0ms
memory: 1232kb

input:

50
268415021
590138010
754876784
937913390
355940776
911253523
260554933
730964311
974778246
5942043...

output:

120404797

result:

ok 1 number(s): "120404797"

Test #3:

score: 10
Accepted
time: 0ms
memory: 1280kb

input:

300
101950659
656431205
452641072
798029135
798932366
94440971
874749233
183737751
826318346
9153952...

output:

426644943

result:

ok 1 number(s): "426644943"

Test #4:

score: 10
Accepted
time: 0ms
memory: 1280kb

input:

300
926032387
288287103
59609871
547058800
31514417
769120932
449758640
879362321
320093778
79140946...

output:

455847635

result:

ok 1 number(s): "455847635"

Test #5:

score: 10
Accepted
time: 3ms
memory: 1792kb

input:

3000
513506508
625942144
548699623
523842250
527990194
627668442
44085509
931065051
761404158
292968...

output:

821817530

result:

ok 1 number(s): "821817530"

Test #6:

score: 10
Accepted
time: 3ms
memory: 1792kb

input:

3000
88977868
431976112
480642599
3339407
7536134
433825556
898912134
423034201
789393381
622616604
...

output:

520573386

result:

ok 1 number(s): "520573386"

Test #7:

score: 10
Accepted
time: 484ms
memory: 38720kb

input:

200000
575599953
347584841
763322860
786706030
291249061
557489637
19661154
92850266
746422101
81163...

output:

767941915

result:

ok 1 number(s): "767941915"

Test #8:

score: 10
Accepted
time: 490ms
memory: 38720kb

input:

200000
213193834
292875878
381304070
239835857
274410721
940670416
58211570
862760907
769957319
8896...

output:

542862980

result:

ok 1 number(s): "542862980"

Test #9:

score: 10
Accepted
time: 495ms
memory: 38724kb

input:

200000
328984979
92574708
256369614
305711520
924334494
168590560
528918555
495141056
849357604
9597...

output:

425914056

result:

ok 1 number(s): "425914056"

Test #10:

score: 10
Accepted
time: 507ms
memory: 38720kb

input:

200000
94748359
776818954
340750244
684072673
886283932
737346853
273321095
526054467
694709118
8542...

output:

530472968

result:

ok 1 number(s): "530472968"

Extra Test:

score: 0
Extra Test Passed

中文 English

Server time: 2025-03-06 02:10:00 | 开源项目