Submission #234124

#TimeUsernameProblemLanguageResultExecution timeMemory
234124anubhavdharMountains (NOI20_mountains)C++14
100 / 100
298 ms20088 KiB
#include<bits/stdc++.h> #define ll long long #define int ll #define pb push_back #define mp make_pair #define FOR(i,n) for(i=0;i<(n);++i) #define FORe(i,n) for(i=1;i<=(n);++i) #define FORr(i,a,b) for(i=(a);i<(b);++i) #define FORrev(i,n) for(i=(n);i>=0;--i) #define F0R(i,n) for(int i=0;i<(n);++i) #define F0Re(i,n) for(int i=1;i<=(n);++i) #define F0Rr(i,a,b) for(ll i=(a);i<(b);++i) #define F0Rrev(i,n) for(int i=(n);i>=0;--i) #define ii pair<ll,ll> #define vi vector<ll> #define vii vector<ii> #define ff first #define ss second #define cd complex<double> #define vcd vector<cd> #define ldd long double #define dbgLine cout<<"Line : "<<__LINE__<<'\n' #define all(x) (x).begin(),(x).end() using namespace std; const int __PRECISION = 10; const ll MOD = 1e9+7; const ll INF = 1e17 + 1101; const ll LOGN = 17; const ll MAXN = 3e5+5; const ll ROOTN = 320; const ldd PI = acos(-1); const ldd EPS = 1e-7; struct SegTree { int st[4*MAXN]; void upd(int node, int ss, int se, int i) { if(ss > i or se < i) return; if(ss == se) { ++st[node]; return; } int mid = (ss + se)/2; upd(node*2 + 1, ss, mid, i); upd(node*2 + 2, mid+1, se, i); st[node] = st[node*2+1] + st[node*2+2]; } ll quer(int node, int ss, int se, int l, int r) { if(ss > r or se < l) return 0; if(ss >= l and se <= r) return st[node]; int mid = (ss + se) / 2; return quer(node*2+1, ss, mid,l,r) + quer(node*2+2,mid+1,se,l,r); } SegTree() { F0R(i, 4*MAXN) st[i] = 0; } inline void update(int i) { upd(0, 0, MAXN, i); } inline ll query(int i, int ded) { ll a = quer(0, 0, MAXN, 0, i-1) - ded, b = quer(0, 0, MAXN, i+1, MAXN); // cout<<"a = "<<a<<", b = "<<b<<'\n'; return (a*b); } } S; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin>>N; pair<ll, int> A[N]; F0R(i, N) { ll j; cin>>j; A[i] = mp(j, i+1); } sort(A, A + N); ll previo = -1, tot = 0, ans = 0; F0R(i, N) { // cout<<"for ("<<A[i].ff<<','<<A[i].ss<<") : "; if(A[i].ff != previo) tot = 0; S.update(A[i].ss); int tmp = S.query(A[i].ss, tot); // cout<<"tot = "<<tot<<", previo = "<<previo<<", no. of combinations is "<<tmp<<'\n'; previo = A[i].ff; ++tot; ans += tmp; } cout<<ans; 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...