Skip to content

Instantly share code, notes, and snippets.

@Wizmann
Created May 25, 2014 11:55
Show Gist options
  • Save Wizmann/8150cfdf1f90ad5dfcbc to your computer and use it in GitHub Desktop.
Save Wizmann/8150cfdf1f90ad5dfcbc to your computer and use it in GitHub Desktop.
HDU 4834 - JZP Set
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define print(x) cout << x << endl
#define input(x) cin >> x
typedef long long llint;
const int SIZE = 100010;
const int MAXN = 10000010;
llint dp[MAXN];
struct Query {
int val;
int pos;
llint ans;
Query(){}
Query(int ival, int ipos): val(ival), pos(ipos) {}
};
Query query[SIZE];
int n;
int cmpByPos(const Query& a, const Query& b)
{
return a.pos < b.pos;
}
int cmpByVal(const Query& a, const Query& b)
{
return a.val < b.val;
}
llint sumA(int x)
{
static int ptr = 1;
static llint sum = 1;
if (x == 0) {
return 0;
}
ptr += 1;
for (/*pass*/; ptr <= x; ptr++) {
// print(ptr << ' ' << sum);
sum += dp[ptr];
// print(ptr << ' ' << sum);
}
ptr -= 1;
return sum;
}
void init()
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i < MAXN; i += 2) {
for (int j = 1; (llint)i * j < MAXN; j++) {
dp[i * j]++;
}
}
for (int i = 1; i < MAXN; i++) {
dp[i] += dp[i - 1];
}
}
int main()
{
freopen("input.txt", "r", stdin);
int v;
input(n);
init();
for (int i = 0; i < n; i++) {
scanf("%d", &v);
query[i] = Query(v, i);
}
sort(query, query + n, cmpByVal);
for (int i = 1, j = 0; i < MAXN && j < n; i++) {
llint f = 1 + i + sumA(i - 1);
while (i == query[j].val) {
query[j].ans = f;
j++;
}
}
sort(query, query +n ,cmpByPos);
for (int i = 0; i < n; i++) {
printf("Case #%d:\n%I64d\n", i + 1, query[i].ans);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment