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; }