Submission #1131715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131715		duckindog	Izbori (COCI22_izbori)	C++17	25 / 110	171 ms	31400 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 200'000 + 10;
int n;
int a[N];

vector<int> pos[N];

namespace IT { 
  struct Node { 
    int cnt;
    long long value;
    Node() : cnt(0), value(0) {}
    Node(int cnt, long long value) : cnt(cnt), value(value) {}
  } f[N << 2];
  long long lazy[N << 2];

  Node merge(Node lt, Node rt) { 
    return {lt.cnt + rt.cnt, lt.value + rt.value};
  }

  inline long long sum(int l, int r) { 
    tie(l, r) = make_pair(-r, -l);
    return 1ll * (r + l) * (r - l + 1) / 2;
  }

  void push(int s, int l, int r) { 
    if (!lazy[s]) return;
    int mid = (l + r) >> 1;
    
    f[s << 1].cnt += 1ll * (mid - l + 1) * lazy[s];   
    f[s << 1].value += sum(l, mid) * lazy[s];
    lazy[s << 1] += lazy[s];

    f[s << 1 | 1].cnt += 1ll * (r - mid) * lazy[s];   
    f[s << 1 | 1].value += sum(mid + 1, r) * lazy[s];
    lazy[s << 1 | 1] += lazy[s];

    lazy[s] = 0;
  }
  void update(int s, int l, int r, int u, int v, int x) { 
    if (v < l || u > r) return;
    if (u <= l && r <= v) { 
      f[s].cnt += 1ll * (r - l + 1) * x;
      f[s].value += sum(l, r) * x;
      lazy[s] += x;
      return;
    }
    push(s, l, r);
    int mid = (l + r) >> 1;
    update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x);
    f[s] = merge(f[s << 1], f[s << 1 | 1]);
  }
  Node query(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return Node();
    if (u <= l && r <= v) return f[s];
    push(s, l, r);
    int mid = (l + r) >> 1;
    return merge(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
    
  }

  inline void update(int l, int r, int x) { 
    update(1, -n, n, l, r, x);
  }
  inline long long query(int l, int r) { 
    auto [cnt, value] = query(1, -n, n, l, r);
    return value - 1ll * cnt * (-r - 1);
  }
}

namespace BIT { 
  int bit[N];
  inline void upd(int i, int x) { 
    for (; i <= n; i += i & -i) bit[i] += x;
  }
  inline int que(int i) { 
    int ret = 0;
    for (; i; i -= i & -i) ret += bit[i];
    return ret;
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];

  vector<int> allValue(a + 1, a + n + 1);
  { // compress
    sort(allValue.begin(), allValue.end());
    allValue.erase(unique(allValue.begin(), allValue.end()), allValue.end());
    for (int i = 1; i <= n; ++i)
      a[i] = upper_bound(allValue.begin(), allValue.end(), a[i]) - allValue.begin();    
  }

  for (int i = 1; i <= n; ++i) pos[i] = {0};
  for (int i = 1; i <= n; ++i) pos[a[i]].push_back(i);
  for (int i = 1; i <= n; ++i) pos[i].push_back(n + 1);

  long long answer = 0;

  IT::update(0, 0, 1);
  for (int i = 1; i <= n; ++i) BIT::upd(i, -1);
  for (int index = 1; index <= (int)allValue.size(); ++index) { 
    if (pos[index][1] != 1) { // pre update
      int p = pos[index][1];
      IT::update(BIT::que(p - 1), BIT::que(1), 1);
    }
    for (int i = 1; i < (int)pos[index].size() - 1; ++i) { 
      int cur = pos[index][i], nxt = pos[index][i + 1];
      BIT::upd(cur, 2);
      int le = BIT::que(nxt - 1), ri = BIT::que(cur);

      answer += IT::query(le - 1, ri - 1);
      answer += 1ll * IT::query(1, -n, n, -n, le - 2).cnt * (ri - le + 1);

      IT::update(le, ri, 1);
    }

    for (int i = (int)pos[index].size() - 2; i >= 1; --i) { 
      int cur = pos[index][i], nxt = pos[index][i + 1];
      int le = BIT::que(nxt - 1), ri = BIT::que(cur);
      IT::update(le, ri, -1);
      BIT::upd(cur, -2);      
    }
    if (pos[index][1] != 1) { // pre update
      int p = pos[index][1];
      IT::update(BIT::que(p - 1), BIT::que(1), -1);
    }
  }

  cout << answer << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 70