Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Author: Mehul Chaturvedi
- Talent is overrated
- */
- #include <bits/stdc++.h>
- using namespace std;
- using ll = int;
- using ld = long double;
- using pll = pair<ll, ll>;
- #define mp make_pair
- #define all(x) (x).begin(), (x).end()
- #define f first
- #define s second
- #define vll vector<long long>
- #define vvll vector<vector<ll>>
- #define vset(v, n, val) \
- v.clear(); \
- v.resize(n, val)
- #define INF 4557430888798830399ll
- #define fr(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
- #define rep(i, n) for (int i = 0, _n = (n); i < _n; i++)
- #define repr(i, n) for (int i = n; i >= 0; i--)
- #define frr(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
- #define trav(a, x) for (auto &a : x)
- #define fil(ar, val) memset(ar, val, sizeof(ar))
- const ll MOD = 1e9 + 7;
- /*
- At each node representin [tl,tr), I store the sorted array from tl to tr-1
- Rest is pretty trivial? Just use lower_bound
- */
- class node {
- public:
- vll arr;
- node(vll val) {
- arr = val;
- }
- };
- vector<ll> v;
- vector<node> t;
- ll n, m;
- ll anss;
- node help(node &left, node &right) {
- vll &arr1 = left.arr;
- vll &arr2 = right.arr;
- vll arr0;
- arr0.resize(arr1.size() + arr2.size());
- merge(all(arr1), all(arr2), arr0.begin());
- node res(arr0);
- return res;
- }
- void build(ll start, ll tl, ll tr) {
- if (tl + 1 == tr) {
- t[start] = node({v[tl]});
- return;
- }
- ll mid = (tl + tr) / 2;
- build(2 * start + 1, tl, mid);
- build(2 * start + 2, mid, tr);
- node &left = t[2 * start + 1];
- node &right = t[2 * start + 2];
- t[start] = help(left, right);
- return;
- }
- ll get(ll start, ll tl, ll tr, ll l, ll r, ll num) {
- if (tl >= r || tr <= l) {
- // anss = 0;
- return 0;
- }
- if (l <= tl && r >= tr) {
- vll &temp = (t[start]).arr;
- ll anss = lower_bound(all(temp), v[l]) - temp.begin();
- return anss;
- }
- ll mid = (tl + tr) / 2;
- ll left = get(2 * start + 1, tl, mid, l, r, num);
- ll right = get(2 * start + 2, mid, tr, l, r, num);
- ll ans = left+right;
- return ans;
- }
- vector<int> solve(vector<int> &nums) {
- t.clear();
- n = nums.size();
- if (n == 0) return {};
- v = nums;
- t.resize(4 * n, node({}));
- build(0, 0, n);
- ll q = nums.size();
- vector<int> ress;
- ll l = 0;
- while (q--) {
- auto temp = get(0, 0, n, l, n, v[l]);
- l++;
- ress.push_back(temp);
- }
- return ress;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement