1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 inline ll re_ad() {
5 char ch=getchar(); ll x=0,f=1;
6 while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
7 while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
8 return x*f;
9 }
10
11 const ll N=3e5+11;
12 ll n,a[N],top,sta[N],L[N][2],R[N][2];
13
14 int main()
15 {
16 freopen("sequence.in","r",stdin);
17 freopen("sequence.out","w",stdout);
18 n=re_ad();
19 for(ll i=1;i<=n;++i) a[i]=re_ad();
20 memset(sta,0,sizeof(sta)); top=0,sta[0]=0;
21 for(ll i=1;i<=n;++i) {
22 while(top && a[i]<a[sta[top]]) --top;
23 L[i][0]=i-sta[top],sta[++top]=i;
24 }
25 memset(sta,0,sizeof(sta)); top=0,sta[0]=n+1;
26 for(ll i=n;i>=1;--i) {
27 while(top && a[i]<=a[sta[top]]) --top;
28 R[i][0]=sta[top]-i,sta[++top]=i;
29 }
30 memset(sta,0,sizeof(sta)); top=0,sta[0]=0;
31 for(ll i=1;i<=n;++i) {
32 while(top && a[i]>=a[sta[top]]) --top;
33 L[i][1]=i-sta[top],sta[++top]=i;
34 }
35 memset(sta,0,sizeof(sta)); top=0,sta[0]=n+1;
36 for(ll i=n;i>=1;--i) {
37 while(top && a[i]>a[sta[top]]) --top;
38 R[i][1]=sta[top]-i,sta[++top]=i;
39 }
40 ll ans=0;
41 for(ll i=1;i<=n;++i) ans+=(L[i][1]*R[i][1]-1)*a[i],ans-=(L[i][0]*R[i][0]-1)*a[i];
42 printf("%lld\n",ans);
43 // for(ll i=1;i<=n;++i) printf("%lld: %lld %lld %lld %lld\n",i,L[i][0],R[i][0],L[i][1],R[i][1]);
44 return 0;
45 }
1 #include<bits/stdc++.h>
2 #define ll long long
3 #define pll pair<ll,ll>
4 using namespace std;
5 inline ll re_ad() {
6 char ch=getchar(); ll x=0,f=1;
7 while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
8 while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
9 return x*f;
10 }
11
12 const ll N=2e5+11;
13 ll n;
14 struct Node { ll x,y; }a[N];
15 priority_queue<ll>q;
16 inline bool cmp(Node A,Node B) { return A.x==B.x?A.y>B.y:A.x<B.x; }
17
18 int main()
19 {
20 freopen("homework.in","r",stdin);
21 freopen("homework.out","w",stdout);
22 n=re_ad();
23 for(ll i=1;i<=n;++i) a[i].x=re_ad(),a[i].y=re_ad();
24 sort(a+1,a+n+1,cmp);
25 ll cnt=0,ans=0;
26 for(ll i=1;i<=n;++i) {
27 if(a[i].x>cnt) q.push(-a[i].y),++cnt,ans+=a[i].y;
28 else if(a[i].y>-q.top()) ans+=a[i].y+q.top(),q.pop(),q.push(-a[i].y);
29 }
30 printf("%lld\n",ans);
31 return 0;
32 }
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 inline ll re_ad() {
5 char ch=getchar(); ll x=0,f=1;
6 while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
7 while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
8 return x*f;
9 }
10
11 const ll N=5e5+11;
12 ll n,num,a[N],b[N],t[N];
13
14 inline ll lowbit(ll d) { return d&(-d); }
15 inline void insert(ll d,ll x) { for(;d<=num;d+=lowbit(d)) t[d]+=x; }
16 inline ll query(ll d) { ll res=0; for(;d;d-=lowbit(d)) res+=t[d]; return res; }
17
18 int main()
19 {
20 freopen("sort.in","r",stdin);
21 freopen("sort.out","w",stdout);
22 n=re_ad();
23 for(ll i=1;i<=n;++i) b[i]=a[i]=re_ad();
24 sort(b+1,b+n+1);
25 num=unique(b+1,b+n+1)-b-1;
26 for(ll i=1;i<=n;++i) a[i]=lower_bound(b+1,b+num+1,a[i])-b;
27 ll ans=0;
28 for(ll i=n;i>=1;--i) ans+=query(a[i]-1),insert(a[i],1);
29 printf("%lld\n",ans);
30 return 0;
31 }
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 inline ll re_ad() {
5 char ch=getchar(); ll x=0,f=1;
6 while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
7 while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
8 return x*f;
9 }
10
11 const ll N=2e6+11,inf=0x3f3f3f3f3f3f3f3f;
12 ll n,m,a[N],tot,dp[N],sum;
13 struct Node { ll pos,val; }t[N];
14
15 namespace F1 {
16 inline void Solve() {
17 ll ans=inf,res=0;
18 for(ll i=1;i<=m;++i) {
19 res=0;
20 for(ll j=2;j<=n;++j) {
21 ll t1=(a[j-1]<a[j]?a[j]-a[j-1]:a[j]+m-a[j-1]);
22 ll t2=(i<=a[j]?a[j]-i:a[j]+m-i)+1;
23 res+=min(t1,t2);
24 // if(i==4) printf("%lld %lld %lld\n",t1,t2,res);
25 }
26 // printf("%lld: %lld\n",i,res);
27 ans=min(ans,res);
28 }
29 printf("%lld\n",ans);
30 }
31 }
32
33 inline void addnode(ll _p,ll _v) { ++tot,t[tot].pos=_p,t[tot].val=_v; }
34 inline bool cmp(Node A,Node B) { return A.pos==B.pos?A.val<B.val:A.pos<B.pos; }
35
36 int main()
37 {
38 freopen("light.in","r",stdin);
39 freopen("light.out","w",stdout);
40 n=re_ad(),m=re_ad();
41 for(ll i=1;i<=n;++i) a[i]=re_ad();
42 if(n<=3e3 && m<=3e3) { F1::Solve(); return 0; }
43 for(ll i=1;i<=n-1;++i) {
44 if(a[i+1]>a[i]) addnode(a[i],1),addnode(a[i+1],a[i]-a[i+1]),sum+=a[i+1]-a[i];
45 else addnode(a[i],1),addnode(a[i+1]+m,a[i]-a[i+1]-m),sum+=a[i+1]+m-a[i];
46 // printf("%lld\n",sum);
47 }
48 sort(t+1,t+tot+1,cmp);
49 // for(ll i=1;i<=tot;++i) printf("%lld: %lld\n",t[i].pos,t[i].val);
50 ll top=1,lj=0,cnt=0,ans=0;
51 for(ll i=1;i<=m*2;++i) {
52 for(;top<=tot && t[top].pos<=i;++top)
53 t[top].val>0?++cnt:(--cnt,lj+=t[top].val);
54 lj+=cnt,dp[i]=lj-cnt;
55 // printf("%lld: %lld %lld %lld\n",i,top,cnt,lj);
56 }
57 for(ll i=1;i<=m;++i) ans=max(ans,dp[i]+dp[i+m]);
58 printf("%lld\n",sum-ans);
59 // printf("sum,ans: %lld %lld\n",sum,ans);
60 return 0;
61 }