Submission #369966

#TimeUsernameProblemLanguageResultExecution timeMemory
369966ivan_tudorMountains (NOI20_mountains)C++14
64 / 100
482 ms262148 KiB
#include<bits/stdc++.h> using namespace std; struct AintNode{ int nl, nr; int val; AintNode *l, *r; AintNode(int _l,int _r, int _val){ nl = _l, nr = _r; val = _val; l = r= NULL; } }; AintNode* update(AintNode *nod,int upoz,int uval){ int l = nod->nl, r = nod->nr; if(r < upoz || upoz < l || uval == 0) return nod; if(l == r){ return new AintNode(l, r, uval); } AintNode *newnode = new AintNode(l, r, 0); int mid = (l + r)/2; if(nod->l == NULL) nod->l = new AintNode(l, mid, 0); newnode->l = update(nod->l, upoz, uval); if(nod->r == NULL) nod->r = new AintNode(mid+1, r, 0); newnode->r = update(nod->r, upoz, uval); newnode->val = newnode->l->val + newnode->r->val; return newnode; } int query(AintNode* node,int ql,int qr){ int l = node->nl, r = node->nr; if(r < ql || l > qr) return 0; if(ql<=l && r<=qr) return node->val; int ans = 0; if(node->l != NULL) ans += query(node->l, ql, qr); if(node->r != NULL) ans += query(node->r, ql, qr); return ans; } const int N = 3*1e5 + 5; long long v[N]; vector<int> poz[N]; AintNode *persist[N]; int main() { //freopen(".in","r",stdin); ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n; cin>>n; map<long long, int> id; for(int i=1;i<=n;i++){ cin>>v[i]; id[v[i]] = 1; } int cnt = 0; for(auto &x:id){ x.second = ++ cnt; } for(int i=1;i<=n;i++){ v[i] = id[v[i]]; poz[v[i]].push_back(i); } AintNode *croot = new AintNode(1, n, 0); persist[0] = croot; for(int i = 1;i< N ; i++){ for(auto pz:poz[i]){ AintNode *newroot = update(croot, pz, 1); croot = newroot; } persist[i] = croot; } long long ans = 0; for(int i=2;i<n;i++){ int val = v[i]; int lval = query(persist[val - 1], 1, i -1); int rval = query(persist[val - 1], i+1, n); ans += 1LL * lval * rval; } 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...