Menu

Hackerearth – Benny and Sum

January 17, 2017 - Hackerearth

Language: C++

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef pair<int, int> II;
struct SQuery {
    int l, r, x, i;
};
 
const int N     = (int) 2e5 + 10;
const int A     = (int) 2e5;
const int MAGIC = 170;
int n, m, a[N];
SQuery Q[N];
 
LL s[N], ans[N];
vector<int> Z[N];
 
struct RSQ {
    static const int MAGIC = 500;
    int a[N], b[N], kurwa[N];
    int Block(int i) { return (i - 1) / MAGIC + 1; }
    int Start(int i) { return (i - 1) * MAGIC + 1; }
    RSQ() {
        for (int i = 1; i <= A; ++i) kurwa[i] = Block(i);
    }
    void Update(int i) {
        if (i == 0) return;
        int x = kurwa[i] + 1;
        for (int j = min(A, Start(x) - 1); j >= i; --j) a[j]++;
        for (int j = kurwa[A]; j >= x; --j) b[j]++;
    }
    inline int Get(int i) {
        return a[i] + b[kurwa[i]];
    }
} RSQ;
 
#ifndef LOCAL
    #define getchar getchar_unlocked
    #define putchar putchar_unlocked
#endif
inline void Read(int &n) {
    char c; n = 0;
    do {
        c = getchar();
    } while (!isdigit(c));
    do {
        n = n * 10 + c - 48;
        c = getchar();
    } while (isdigit(c));
}
inline void Write(LL n) {
    if (n == 0) {
        puts("0");
        return;
    }
    int a[20], k = 0;
    while (n) {
        a[++k] = n % 10;
        n /= 10;
    }
    for (int i = k; i >= 1; --i) putchar(a[i] + 48);
    putchar('\n');
}
 
int b[N];
bool cmp(int x, int y) { return a[x] < a[y]; }
bool c1(SQuery a, SQuery b) { return a.l < b.l; }
bool c2(SQuery a, SQuery b) { return a.r < b.r; }
 
int main() {
    #ifdef LOCAL
        freopen("Data.inp", "r", stdin);
        freopen("Data.out", "w", stdout);
    #endif
 
    Read(n); Read(m);
    for (int i = 1; i <= n; ++i) Read(a[i]);
    for (int i = 1; i <= m; ++i) Read(Q[i].l), Read(Q[i].r), Read(Q[i].x), Q[i].i = i;
 
    for (int i = 1; i <= n; ++i) b[i] = i;
    sort(b + 1, b + 1 + n, cmp);
    for (int i = 1; i <= m; ++i) if (Q[i].x <= MAGIC) Z[Q[i].x].push_back(i);
    for (int x = 1; x <= MAGIC; ++x) {
        for (int i = 1, t = 0, g = x; i <= n; ++i) {
            while (a[b[i]] >= g) t++, g += x;
            s[b[i]] = x - g;
        }
        for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + s[i] + a[i];
        for (int i = 0; i < (int) Z[x].size(); ++i) {
            int p = Z[x][i];
            ans[p] = s[Q[p].r] - s[Q[p].l - 1];
        }
    }
 
    sort(Q + 1, Q + 1 + m, c1);
    for (int i = 1, y = 0; i <= m; ++i) if (Q[i].x > MAGIC) {
        while (y + 1 <= Q[i].l - 1) RSQ.Update(a[++y]);
        for (int j = Q[i].x - 1, t = 1; j < A; j += Q[i].x, ++t) {
            LL c = RSQ.Get(min(A, j + Q[i].x)) - RSQ.Get(j);
            ans[Q[i].i] -= t * c;
        }
    }
    for (int i = 1; i <= A; ++i) RSQ.a[i] = RSQ.b[i] = 0;
    sort(Q + 1, Q + 1 + m, c2);
    for (int i = 1, y = 0; i <= m; ++i) if (Q[i].x > MAGIC)  {
        while (y + 1 <= Q[i].r) RSQ.Update(a[++y]);
        for (int j = Q[i].x - 1, t = 1; j < A; j += Q[i].x, ++t) {
            LL c = RSQ.Get(min(A, j + Q[i].x)) - RSQ.Get(j);
            ans[Q[i].i] += t * c;
        }
    }
 
    for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
    for (int i = 1; i <= m; ++i)
        if (Q[i].x > MAGIC) ans[Q[i].i] = s[Q[i].r] - s[Q[i].l - 1] - ans[Q[i].i] * Q[i].x;
 
    for (int i = 1; i <= m; ++i) Write(ans[i]);
    return 0;
}

(246)

It's only fair to share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on VK

Author of this post : UnknownA AuthorA

Leave a Reply

Your email address will not be published. Required fields are marked *