Codeforces Round #378 (Div. 2), problem: (E) Sleep in Class Solution in C

#include
#define ABS(a) ((a) < 0 ? (a) : (a))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define TRUE 1
#define FALSE 0

#define getchar_unlocked() getchar()

long long fast_in()
{
static long long j_fast;
static char c_fast;
j_fast = 0;
c_fast = getchar_unlocked();
while (c_fast < ‘0’ || c_fast > ‘9’)
c_fast = getchar_unlocked();
while (c_fast >= ‘0’ && c_fast <= ‘9’) {
j_fast = (j_fast << 1) + (j_fast << 3) + c_fast – ‘0’;
c_fast = getchar_unlocked();
}
return j_fast;
}

#define MAXN 1000006

long long n, a[MAXN], ans[MAXN], down[MAXN], up[MAXN], wdown[MAXN], wup[MAXN];

long long binary_search_up(long long req)
{
// search for last occurance
static long long f, l, m;
f = 1;
l = n + 1;
while ((l – f) > 1) {
m = ((l + f) >> 1);
if (up[m] >= req)
f = m;
else
l = m;
}
if (up[l] == req)
return l;
else
return f;
}
long long binary_search_down(long long req)
{
// search for first occurance
static long long f, l, m;
f = 0;
l = n;
while ((l – f) > 1) {
m = ((l + f) >> 1);
if (down[m] < req)
f = m;
else
l = m;
}
if (down[f] == req)
return f;
else
return l;
}
int main()
{
static long long i, considered, uptill, downtill;
static char c;
n = fast_in();
for (i = 1; i <= n; i++) {
c = getchar_unlocked();
if (c == ‘U’)
a[i] = 1;
else
a[i] = 0;
}
for (i = 1; i <= n; i++) {
if (a[i])
down[i] = down[i – 1];
else
down[i] = down[i – 1] + 1;
}
for (i = 0; i <= n; i++) {
if (a[i])
wdown[i] = wdown[i – 1];
else
wdown[i] = wdown[i – 1] + i;
}
for (i = n; i > 0; i–) {
if (a[i])
up[i] = up[i + 1] + 1;
else
up[i] = up[i + 1];
}
for (i = n; i > 0; i–) {
if (a[i])
wup[i] = wup[i + 1] + (n – i + 1);
else
wup[i] = wup[i + 1];
}
up[0] = up[1];
wup[0] = wup[1];
down[n + 1] = down[n];
wdown[n + 1] = wdown[n];
// for (i = 0; i <= n + 1; i++) {
// printf(“%lld %lld %lld %lld\n”, up[i], down[i], wup[i],
// wdown[i]);
// }
for (i = 1; i <= n; i++) {
considered = MIN(up[0] – up[i], down[n] – down[i]);
if (a[i]) {
downtill = binary_search_down(considered + down[i] + 1);
uptill = binary_search_up(considered + up[i]);
} else {
downtill = binary_search_down(considered + down[i]);
uptill = binary_search_up(considered + up[i] + 1);
}
ans[i] = (wdown[downtill] – wdown[i] –
i * (down[downtill] – down[i]));
ans[i] +=
(wup[uptill] – wup[i] – (n – i + 1) * (up[uptill] – up[i]));
ans[i] <<= 1;

//printf(“%lld considered %lld downtill %lld uptill %lld\n”, i,
// considered, downtill, uptill);
if (a[i]) {
if ((down[n] – down[i]) > (up[0] – up[i]))
ans[i] += i;
else
ans[i] += (n – i + 1);
} else {
if ((down[n] – down[i]) >= (up[0] – up[i]))
ans[i] += i;
else
ans[i] += (n – i + 1);
}
}
for (i = 1; i <= n; i++)
printf(“%lld “, ans[i]);
return 0;
}