Editorial for Bedao Grand Contest 04 - SUDI
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Code mẫu
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+1; int n; ll a[N]; ll Mx[100001][20]; ll Mn[100001][20]; map<ll,int> trc; ll res; void init() { for (int i=1;i<=n;i++) Mx[i][0]=Mn[i][0]=a[i]; for (int k=1; (1<<k)<=n; k++) for (int i=1; i+(1<<k)-1<=n; i++) { Mx[i][k] = max(Mx[i][k-1],Mx[i+(1<<(k-1))][k-1]); Mn[i][k] = min(Mn[i][k-1],Mn[i+(1<<(k-1))][k-1]); } } ll getmx(int u,int v) { int k=log2(v-u+1); return max(Mx[u][k],Mx[v-(1<<k)+1][k]); } ll getmn(int u,int v) { int k=log2(v-u+1); return min(Mn[u][k],Mn[v-(1<<k)+1][k]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); freopen("SUDI.inp","r",stdin); freopen("SUDI.out","w",stdout); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } init(); for(int i=1;i<=n;i++) { int dau=trc[a[i]]+1,cuoi=i,giua; int posl=i; while(dau<=cuoi) { giua=(dau+cuoi)/2; if(getmx(giua,i)==a[i]) { posl=giua; cuoi=giua-1; } else dau=giua+1; } dau=i,cuoi=n; int posr=i; while(dau<=cuoi) { giua=(dau+cuoi)/2; if(getmx(i,giua)==a[i]) { posr=giua; dau=giua+1; } else cuoi=giua-1; } res+=1LL*(posr-i+1)*(i-posl+1)*a[i]; dau=trc[a[i]]+1,cuoi=i,giua; posl=i; while(dau<=cuoi) { giua=(dau+cuoi)/2; if(getmn(giua,i)==a[i]) { posl=giua; cuoi=giua-1; } else dau=giua+1; } dau=i,cuoi=n; posr=i; while(dau<=cuoi) { giua=(dau+cuoi)/2; if(getmn(i,giua)==a[i]) { posr=giua; dau=giua+1; } else cuoi=giua-1; } res-=1LL*(posr-i+1)*(i-posl+1)*a[i]; trc[a[i]]=i; } cout<<res; return 0; }
Comments