Submission #224860

#TimeUsernameProblemLanguageResultExecution timeMemory
224860bukanYohandiMountains (NOI20_mountains)C++14
100 / 100
267 ms33528 KiB
#include <bits/stdc++.h> #define fs first #define sc second #define pb push_back #define eb emplace_back #define all(a) a.begin(),a.end() #define lb(a,x) (lower_bound(all(a),x)-a.begin()) #define ub(a,x) (upper_bound(all(a),x)-a.begin()) #define rep(a,x,y) for(int a=(int)x;a<=(int)y;++a) #define repd(a,x,y,d) for(int a=(int)x;a<=(int)y;a+=d) #define res(a,x,y) for(int a=(int)x;a>=(int)y;--a) #define resd(a,x,y,d) for(int a=(int)x;a>=(int)y;a-=d) // Ordered Set, Ordered Multiset #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define o_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> #define o_multiset tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> using namespace __gnu_pbds; // .order_of_key(x) -> Number of elements less than x // * .find_by_order(k) -> Kth smallest element (0-based) // .erase(x) -> Remove all elements equal to x #pragma GCC optimize("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; using lint=long long; mt19937 rng(time(NULL)); lint Power(lint A,lint B,lint C){ if(!B) return 1LL; lint tmp=Power(A,B>>1,C); return tmp*tmp%C*(B&1?A:1)%C; } struct Q{lint L,R,Idx,X;}; struct Smth{lint Idx,Val;} Arr[333333]; int T,N; lint Ans,Le,Ri; lint Bit[333333],H[333333],Prefix[111][333333]; lint Jwb[666666]; Q Query[666666]; lint Sum(int Idx){ lint Ret=0; for(;Idx>0;Idx-=Idx&-Idx) Ret+=Bit[Idx]; return Ret; } void Upd(int Idx){for(;Idx<=N+5;Idx+=Idx&-Idx) Bit[Idx]++;} bool Cmp(Q A,Q B){return A.X<B.X;} bool Cmp2(Smth A,Smth B){return A.Val<B.Val;} int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); T=1; // cin>>T; rep(t,1,T){ cin>>N; for(int i=1;i<=N;++i) cin>>H[i]; for(int i=2;i<=N-1;++i){ Query[2*i-1].L=1; Query[2*i-1].R=i-1; Query[2*i-1].Idx=2*i-1; Query[2*i-1].X=H[i]; Query[2*i].L=i+1; Query[2*i].R=N; Query[2*i].Idx=2*i; Query[2*i].X=H[i]; } for(int i=1;i<=N;++i){ Arr[i].Idx=i; Arr[i].Val=H[i]; } sort(Arr+1,Arr+N+1,Cmp2); sort(Query+3,Query+2*N-1,Cmp); int Cur=1; for(int i=3;i<=2*N-2;++i){ for(;Arr[Cur].Val<Query[i].X&&Cur<=N;Cur++) Upd(Arr[Cur].Idx); Jwb[Query[i].Idx]=Sum(Query[i].R)-Sum(Query[i].L-1); } for(int i=2;i<=N-1;++i) Ans+=(lint)Jwb[2*i-1]*Jwb[2*i]; cout<<Ans<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...