結果

問題 No.924 紲星
ユーザー akakimidoriakakimidori
提出日時 2020-02-08 01:22:54
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 2,720 ms / 4,000 ms
コード長 3,022 bytes
コンパイル時間 1,322 ms
コンパイル使用メモリ 32,000 KB
実行使用メモリ 181,928 KB
最終ジャッジ日時 2024-09-25 08:31:20
合計ジャッジ時間 21,515 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2,477 ms
181,668 KB
testcase_09 AC 2,720 ms
181,800 KB
testcase_10 AC 2,529 ms
181,796 KB
testcase_11 AC 2,432 ms
181,800 KB
testcase_12 AC 2,520 ms
181,928 KB
testcase_13 AC 935 ms
61,920 KB
testcase_14 AC 821 ms
38,464 KB
testcase_15 AC 805 ms
49,120 KB
testcase_16 AC 838 ms
155,520 KB
testcase_17 AC 1,421 ms
63,092 KB
testcase_18 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;
typedef int64_t i64;

#define ALLOC(size,type) ((type*)calloc((size),sizeof(type)))
#define SORT(a,num,cmp) qsort((a),(num),sizeof(*(a)),cmp)

typedef struct node {
    i64 sum;
    i64 cnt;
    const struct node *left;
    const struct node *right;
} node;

void eval(const node *t, i64 *sum, i64 *cnt) {
    if (t != NULL) {
        *sum += t->sum;
        *cnt += t->cnt;
    }
}

node* new_node(const node *l, const node *r) {
    node *t = ALLOC (1, node);
    eval (l, &t->sum, &t->cnt);
    eval (r, &t->sum, &t->cnt);
    t->left = l;
    t->right = r;
    return t;
}

const node* update(const node *t, i32 l, i32 r, i32 x, i64 v) {
    if (l + 1 == r) {
        node *t = new_node(NULL, NULL);
        t->sum = v;
        t->cnt = 1;
        return t;
    }
    const node *left = NULL;
    const node *right = NULL;
    if (t != NULL) {
        left = t->left;
        right = t->right;
    }
    i64 m = (l + r) / 2;
    if (x < m) {
        left = update (left, l, m, x, v);
    } else {
        right = update (right, m, r, x, v);
    }
    return new_node (left, right);
}

void find (const node *t, i32 l, i32 r, i32 x, i32 y, i64 *sum, i64 *cnt) {
    if (t == NULL || r <= x || y <= l) {
        return;
    }
    if (x <= l && r <= y) {
        eval (t, sum, cnt);
        return;
    }
    i64 m = (l + r) / 2;
    find (t->left, l, m, x, y, sum, cnt);
    find (t->right, m, r, x, y, sum, cnt);
}

int cmp_int (const void *a, const void *b) {
    i64 p = *(const i64 *)a;
    i64 q = *(const i64 *)b;
    return p == q ? 0 : p <= q ? -1 : 1;
}

void run (void) {
    i32 n, q;
    scanf ("%" SCNi32 "%" SCNi32, &n, &q);
    i64 *a = ALLOC (n, i64);
    i64 *s = ALLOC (n + 1, i64);
    for (i32 i = 0; i < n; ++i) {
        i64 b;
        scanf ("%" SCNi64, &b);
        a[i] = (b << 18) + i;
        s[i] = b;
    }
    for (i32 i = n - 1; i >= 0; --i) {
        s[i] += s[i + 1];
    }
    SORT (a, n, cmp_int);
    const node **seg = ALLOC (n + 1, const node *);
    for (i32 i = 0; i < n; ++i) {
        i64 v = a[i] >> 18;
        i32 k = a[i] & ((1 << 18) - 1);
        seg[i + 1] = update (seg[i], 0, n, k, v);
    }
    for (i32 i = 0; i < q; ++i) {
        i32 l, r;
        scanf ("%" SCNi32 "%" SCNi32, &l, &r);
        l -= 1;
        i32 ng = 0;
        i32 ok = n;
        while (ok - ng > 1) {
            i32 mid = (ok + ng) / 2;
            i64 sum = 0;
            i64 cnt = 0;
            find (seg[mid], 0, n, l, r, &sum, &cnt);
            if (2 * cnt >= r - l) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        i64 sum = 0;
        i64 cnt = 0;
        find (seg[ok], 0, n, l, r, &sum, &cnt);
        i64 ans = 0;
        ans += s[l] - s[r] - sum - (r - l - cnt) * (a[ok - 1] >> 18);
        ans += cnt * (a[ok - 1] >> 18) - sum;
        printf ("%" PRIi64 "\n", ans);
    }
}

int main (void) {
    run();
    return 0;
}
0