Submission #645770

#TimeUsernameProblemLanguageResultExecution timeMemory
645770kith14Mountains (NOI20_mountains)C++17
100 / 100
318 ms27176 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define db double #define pairll pair<ll,ll> #define lpairll pair<ll,pairll> #define repp(i,a,b) for (ll i = a; i <= b; i++) #define repz(i,a,b) for (ll i = a; i < b; i++) #define repm(i,a,b) for (ll i = a; i >= b; i--) #define fr first #define sc second #define mp make_pair #define pb push_back const ll N = 3e5+5, MOD = 1e9+7; ll tc = 1, n, m, ar[N], lr[N], rr[N], tree[N*4]; string s, s1, s2, ye = "YA", no = "TIDAK"; vector<pairll> v; void input(){ cin >> n; repp(i,1,n){ cin >> ar[i]; v.pb(mp(ar[i],i)); } sort(v.begin(),v.end()); ll pre = -1, cnt = 0; for (auto i : v){ if (i.fr != pre){ pre = i.fr; cnt++; } ar[i.sc] = cnt; } } void upd(ll l, ll r, ll idx, ll pos, ll val){ if (l == r){ tree[idx] += val; return; } ll md = (l+r)/2; if (pos <= md) upd(l,md,idx*2,pos,val); else upd(md+1,r,idx*2+1,pos,val); tree[idx] = tree[idx*2]+tree[idx*2+1]; } ll que(ll l, ll r, ll idx, ll x, ll y){ if (x > y || l > r || l > y || r < x) return 0; if (x <= l && r <= y) return tree[idx]; ll md = (l+r)/2; return que(l,md,idx*2,x,y)+que(md+1,r,idx*2+1,x,y); } void solve(){ memset(tree,0,sizeof(tree)); repp(i,1,n){ lr[i] = que(1,n,1,1,ar[i]-1); upd(1,n,1,ar[i],1); } memset(tree,0,sizeof(tree)); repm(i,n,1){ rr[i] = que(1,n,1,1,ar[i]-1); upd(1,n,1,ar[i],1); } ll ans = 0; repp(i,1,n){ ans += lr[i]*rr[i]; //cout << i << " " << lr[i] << " " << rr[i] << endl; } cout << ans << endl; } int main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); //cin >> tc; while(tc--){ input(); solve(); } }
#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...