Submission #369977

#	Time	Username	Problem	Language	Result	Execution time	Memory
369977		ivan_tudor	Mountains (NOI20_mountains)	C++14	64 / 100	490 ms	262148 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
struct AintNode{
  int nl, nr;
  int val;
  AintNode *l, *r;
  AintNode(){
    nl = nr = val = 0;
    l = r = NULL;
  }
  AintNode(int _l, int _r, int _val);
};
AintNode *NIL = new AintNode;
AintNode :: AintNode(int _l,int _r, int _val){
    nl = _l, nr = _r;
    val = _val;
    l = r= NIL;
  }
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;
  *newnode = *nod;
  int mid = (l + r)/2;
  if(upoz <= mid){
    if(nod->l == NIL)
      nod->l = new AintNode(l, mid, 0);
    newnode->l = update(nod->l, upoz, uval);
  }
  else{
    if(nod->r == NIL)
      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 != NIL)
    ans += query(node->l, ql, qr);
  if(node->r != NIL)
    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;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 0 / 9
• Subtask 7: 0 / 12