#1173727 (C(gnu17)) No.480 合計

• 問題: No.480 合計
• ユーザー: Shorter
• 提出日時: 2026-07-26 13:31:45
• 言語: C(gnu17) (gcc 15.2.0)
• 結果: AC
• 実行時間: 0 ms / 2,000 ms
• コード長: 18,765 bytes
• コンパイル時間: 2,002 ms
• コンパイル使用メモリ: 125,292 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-07-26 13:31:49
• 合計ジャッジ時間: 3,234 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

ファイルパターン	結果
other	AC * 22

ソースコード

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,sse4.2")


#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <immintrin.h>

#define FASTIO_ALWAYS_INLINE static inline __attribute__((always_inline))
#define FASTIO_OUT_BUF_SIZE (1u << 20)
#define FASTIO_MAX_INT_DIGITS 32

typedef struct FastInput {
    const char *base;
    const char *ptr;
    const char *end;
    size_t map_len;
    int is_mapped;
} FastInput;

typedef struct FastOutput {
    int fd;
    char *buf;
    size_t cap;
    size_t len;
} FastOutput;

typedef struct FastIO {
    FastInput in;
    FastOutput out;
} FastIO;

static inline void fastio__write_all(int fd, const char *__restrict__ buf, size_t len) {
    size_t off = 0;
    while (off < len) {
        ssize_t w = write(fd, buf + off, len - off);
        if (w < 0) {
            if (errno == EINTR) continue;
            _exit(1);
        }
        off += (size_t)w;
    }
}

static inline void fastio__read_all_fallback(FastInput *in, int fd) {
    size_t cap = 1u << 20;
    size_t len = 0;
    char  *buf = (char *)malloc(cap);
    for (;;) {
        if (len == cap) {
            cap <<= 1;
            buf = (char *)realloc(buf, cap);
        }
        ssize_t r = read(fd, buf + len, cap - len);
        if (r < 0) {
            if (errno == EINTR) continue;
            _exit(1);
        }
        if (r == 0) break;
        len += (size_t)r;
    }
    in->base = buf;
    in->ptr = buf;
    in->end = buf + len;
    in->map_len = 0;
    in->is_mapped = 0;
}

static inline void fastio_init(FastIO *io, int in_fd, int out_fd) {
    struct stat st;
    if (fstat(in_fd, &st) == 0 && S_ISREG(st.st_mode) && st.st_size > 0) {
        void *p = mmap(NULL, (size_t)st.st_size, PROT_READ, MAP_PRIVATE, in_fd, 0);
        if (p != MAP_FAILED) {
            io->in.base = (const char *)p;
            io->in.ptr = io->in.base;
            io->in.end = io->in.base + (size_t)st.st_size;
            io->in.map_len = (size_t)st.st_size;
            io->in.is_mapped = 1;
        } else {
            fastio__read_all_fallback(&io->in, in_fd);
        }
    } else if (fstat(in_fd, &st) == 0 && S_ISREG(st.st_mode) && st.st_size == 0) {
        io->in.base = NULL;
        io->in.ptr = NULL;
        io->in.end = NULL;
        io->in.map_len = 0;
        io->in.is_mapped = 0;
    } else {
        fastio__read_all_fallback(&io->in, in_fd);
    }

    io->out.fd = out_fd;
    io->out.cap = FASTIO_OUT_BUF_SIZE;
    io->out.buf = (char *)aligned_alloc(64, io->out.cap);
    io->out.len = 0;
}

static inline void fastio_flush(FastIO *io) {
    if (io->out.len > 0) {
        fastio__write_all(io->out.fd, io->out.buf, io->out.len);
        io->out.len = 0;
    }
}

static inline void fastio_destroy(FastIO *io) {
    fastio_flush(io);
    free(io->out.buf);
    io->out.buf = NULL;
    if (io->in.base) {
        if (io->in.is_mapped) {
            munmap((void *)io->in.base, io->in.map_len);
        } else {
            free((void *)io->in.base);
        }
    }
    io->in.base = io->in.ptr = io->in.end = NULL;
}

static inline void fastio__skip_ws(FastInput *__restrict__ in) {
    const char *p = in->ptr;
    const char *end = in->end;

    const __m256i sp = _mm256_set1_epi8(' ');
    const __m256i nl = _mm256_set1_epi8('\n');
    const __m256i cr = _mm256_set1_epi8('\r');
    const __m256i tb = _mm256_set1_epi8('\t');

    while (p + 32 <= end) {
        __m256i v = _mm256_loadu_si256((const __m256i *)p);
        __m256i is_ws = _mm256_or_si256(
            _mm256_or_si256(_mm256_cmpeq_epi8(v, sp), _mm256_cmpeq_epi8(v, nl)),
            _mm256_or_si256(_mm256_cmpeq_epi8(v, cr), _mm256_cmpeq_epi8(v, tb)));
        unsigned mask = (unsigned)_mm256_movemask_epi8(is_ws);
        if (mask != 0xFFFFFFFFu) {
            unsigned non_ws = ~mask;
            p += __builtin_ctz(non_ws);
            in->ptr = p;
            return;
        }
        p += 32;
    }
    while (p < end) {
        char c = *p;
        if (c == ' ' || c == '\n' || c == '\r' || c == '\t') {
            ++p;
        } else {
            break;
        }
    }
    in->ptr = p;
}

static inline uint32_t fastio__parse8(uint64_t val) {
    const uint64_t mask = 0x000000FF000000FFULL;
    const uint64_t mul1 = 0x000F424000000064ULL;
    const uint64_t mul2 = 0x0000271000000001ULL;
    val -= 0x3030303030303030ULL;
    val = (val * 10) + (val >> 8);
    val = (((val & mask) * mul1) + (((val >> 16) & mask) * mul2)) >> 32;
    return (uint32_t)val;
}

static inline uint64_t fastio__parse_udigits(FastInput *__restrict__ in) {
    const char *p = in->ptr;
    const char *end = in->end;
    uint64_t acc = 0;

    const __m256i lo_bound = _mm256_set1_epi8('0' - 1);
    const __m256i hi_bound = _mm256_set1_epi8('9' + 1);

    while (p + 32 <= end) {
        __m256i v = _mm256_loadu_si256((const __m256i *)p);
        __m256i ge = _mm256_cmpgt_epi8(v, lo_bound);
        __m256i le = _mm256_cmpgt_epi8(hi_bound, v);
        __m256i is_digit = _mm256_and_si256(ge, le);
        unsigned mask = (unsigned)_mm256_movemask_epi8(is_digit);

        if (mask == 0xFFFFFFFFu) {
            for (int k = 0; k < 32; k += 8) {
                uint64_t chunk;
                memcpy(&chunk, p + k, 8);
                acc = acc * 100000000ULL + fastio__parse8(chunk);
            }
            p += 32;
            continue;
        }

        unsigned non_digit = ~mask;
        int run = __builtin_ctz(non_digit);
        int k = 0;
        for (; k + 8 <= run; k += 8) {
            uint64_t chunk;
            memcpy(&chunk, p + k, 8);
            acc = acc * 100000000ULL + fastio__parse8(chunk);
        }
        for (; k < run; ++k) {
            acc = acc * 10 + (uint64_t)(unsigned char)(p[k] - '0');
        }
        p += run;
        in->ptr = p;
        return acc;
    }

    while (p < end) {
        unsigned char c = (unsigned char)*p;
        if (c < '0' || c > '9') break;
        acc = acc * 10 + (uint64_t)(c - '0');
        ++p;
    }
    in->ptr = p;
    return acc;
}

static inline size_t fastio__scan_token_len(const char *__restrict__ p, const char *__restrict__ end) {
    const char *start = p;
    const __m256i sp = _mm256_set1_epi8(' ');
    const __m256i nl = _mm256_set1_epi8('\n');
    const __m256i cr = _mm256_set1_epi8('\r');
    const __m256i tb = _mm256_set1_epi8('\t');

    while (p + 32 <= end) {
        __m256i v = _mm256_loadu_si256((const __m256i *)p);
        __m256i is_ws = _mm256_or_si256(
            _mm256_or_si256(_mm256_cmpeq_epi8(v, sp), _mm256_cmpeq_epi8(v, nl)),
            _mm256_or_si256(_mm256_cmpeq_epi8(v, cr), _mm256_cmpeq_epi8(v, tb)));
        unsigned mask = (unsigned)_mm256_movemask_epi8(is_ws);
        if (mask != 0) {
            return (size_t)(p - start) + (size_t)__builtin_ctz(mask);
        }
        p += 32;
    }
    while (p < end) {
        char c = *p;
        if (c == ' ' || c == '\n' || c == '\r' || c == '\t') break;
        ++p;
    }
    return (size_t)(p - start);
}

static inline int64_t fastio_read_i64(FastIO *io) {
    fastio__skip_ws(&io->in);
    int neg = 0;
    if (io->in.ptr < io->in.end && *io->in.ptr == '-') {
        neg = 1;
        ++io->in.ptr;
    }
    uint64_t u = fastio__parse_udigits(&io->in);
    if (!neg) return (int64_t)u;
    return -(int64_t)(u - 1) - 1;
}

static inline int32_t fastio_read_i32(FastIO *io) {
    return (int32_t)fastio_read_i64(io);
}

static inline uint64_t fastio_read_u64(FastIO *io) {
    fastio__skip_ws(&io->in);
    return fastio__parse_udigits(&io->in);
}

static inline uint32_t fastio_read_u32(FastIO *io) {
    return (uint32_t)fastio_read_u64(io);
}

static inline char fastio_read_char(FastIO *io) {
    fastio__skip_ws(&io->in);
    if (io->in.ptr >= io->in.end) return '\0';
    return *io->in.ptr++;
}

static inline bool fastio_read_bool(FastIO *io) {
    fastio__skip_ws(&io->in);
    if (io->in.ptr >= io->in.end) return false;
    char c = *io->in.ptr++;
    return c != '0';
}

static inline size_t fastio_read_str(FastIO *io, char *dst, size_t dst_cap) {
    fastio__skip_ws(&io->in);
    size_t len = fastio__scan_token_len(io->in.ptr, io->in.end);
    size_t copy_len = (dst_cap > 0 && len >= dst_cap) ? dst_cap - 1 : len;
    if (copy_len > 0) memcpy(dst, io->in.ptr, copy_len);
    if (dst_cap > 0) dst[copy_len] = '\0';
    io->in.ptr += len;
    return copy_len;
}

static inline size_t fastio_read_str_view(FastIO *io, const char **out_ptr) {
    fastio__skip_ws(&io->in);
    size_t len = fastio__scan_token_len(io->in.ptr, io->in.end);
    *out_ptr = io->in.ptr;
    io->in.ptr += len;
    return len;
}

static inline void fastio__ensure(FastIO *__restrict__ io, size_t need) {
    if (__builtin_expect(io->out.len + need > io->out.cap, 0)) {
        fastio_flush(io);
    }
}

static inline void fastio_write_char(FastIO *__restrict__ io, char c) {
    fastio__ensure(io, 1);
    io->out.buf[io->out.len++] = c;
}

static inline void fastio_write_newline(FastIO *io) {
    fastio_write_char(io, '\n');
}

static inline void fastio_write_bool(FastIO *io, bool b) {
    fastio_write_char(io, b ? '1' : '0');
}

FASTIO_ALWAYS_INLINE void fastio__simd_copy(char *__restrict__ dst, const char *__restrict__ src, size_t len) {
    size_t i = 0;
    for (; i + 32 <= len; i += 32) {
        __m256i v = _mm256_loadu_si256((const __m256i *)(src + i));
        _mm256_storeu_si256((__m256i *)(dst + i), v);
    }
    if (i < len) memcpy(dst + i, src + i, len - i);
}

static inline void fastio_write_str(FastIO *__restrict__ io, const char *__restrict__ s, size_t len) {
    if (len >= io->out.cap) {
        fastio_flush(io);
        fastio__write_all(io->out.fd, s, len);
        return;
    }
    fastio__ensure(io, len);
    if (len >= 32) {
        fastio__simd_copy(io->out.buf + io->out.len, s, len);
    } else {
        memcpy(io->out.buf + io->out.len, s, len);
    }
    io->out.len += len;
}

static inline void fastio_write_cstr(FastIO *io, const char *s) {
    fastio_write_str(io, s, strlen(s));
}

static uint32_t *fastio__lut1 = NULL;
static uint32_t *fastio__lut2 = NULL;

__attribute__((constructor))
static void fastio__build_luts(void) {
    fastio__lut1 = (uint32_t *)malloc(10000 * sizeof(uint32_t));
    fastio__lut2 = (uint32_t *)malloc(10000 * sizeof(uint32_t));
    for (int i = 0; i < 10000; ++i) {
        char b1[4];
        b1[0] = (i >= 1000) ? (char)('0' + (i / 1000) % 10) : ' ';
        b1[1] = (i >= 100)  ? (char)('0' + (i / 100) % 10)  : ' ';
        b1[2] = (i >= 10)   ? (char)('0' + (i / 10) % 10)   : ' ';
        b1[3] = (char)('0' + i % 10);
        memcpy(&fastio__lut1[i], b1, 4);

        char b2[4];
        b2[0] = (char)('0' + (i / 1000) % 10);
        b2[1] = (char)('0' + (i / 100) % 10);
        b2[2] = (char)('0' + (i / 10) % 10);
        b2[3] = (char)('0' + i % 10);
        memcpy(&fastio__lut2[i], b2, 4);
    }
}

__attribute__((destructor))
static void fastio__free_luts(void) {
    free(fastio__lut1);
    free(fastio__lut2);
    fastio__lut1 = NULL;
    fastio__lut2 = NULL;
}

FASTIO_ALWAYS_INLINE int fastio__sig4(uint32_t hi) {
    if (hi < 10) return 1;
    if (hi < 100) return 2;
    if (hi < 1000) return 3;
    return 4;
}

FASTIO_ALWAYS_INLINE int fastio__emit_lead_fwd(char *__restrict__ dst, uint32_t hi) {
    int sig = fastio__sig4(hi);
    uint32_t sv = fastio__lut1[hi] >> ((4 - sig) * 8);
    memcpy(dst, &sv, 4);
    return sig;
}

static inline void fastio_write_u32(FastIO *io, uint32_t val) {
    int nblocks;
    if (val < 10000u) nblocks = 1;
    else if (val < 100000000u) nblocks = 2;
    else nblocks = 3;

    fastio__ensure(io, (size_t)nblocks * 4);
    char *dst = io->out.buf + io->out.len;
    int total_len;

    if (nblocks == 1) {
        total_len = fastio__emit_lead_fwd(dst, val);
    } else if (nblocks == 2) {
        uint32_t hi = val / 10000u;
        uint32_t lo = val % 10000u;
        int sig = fastio__emit_lead_fwd(dst, hi);
        memcpy(dst + sig, &fastio__lut2[lo], 4);
        total_len = sig + 4;
    } else {
        uint32_t hi = val / 100000000u;
        uint32_t rem = val % 100000000u;
        uint32_t b1 = rem / 10000u;
        uint32_t b2 = rem % 10000u;
        int sig = fastio__emit_lead_fwd(dst, hi);
        memcpy(dst + sig, &fastio__lut2[b1], 4);
        memcpy(dst + sig + 4, &fastio__lut2[b2], 4);
        total_len = sig + 8;
    }
    io->out.len += (size_t)total_len;
}

static inline void fastio_write_u64(FastIO *io, uint64_t val) {
    int nblocks;
    if (val < 10000ULL) nblocks = 1;
    else if (val < 100000000ULL) nblocks = 2;
    else if (val < 1000000000000ULL) nblocks = 3;
    else if (val < 10000000000000000ULL) nblocks = 4;
    else nblocks = 5;

    fastio__ensure(io, (size_t)nblocks * 4);
    char *dst = io->out.buf + io->out.len;
    int total_len;

    switch (nblocks) {
    case 1: {
        total_len = fastio__emit_lead_fwd(dst, (uint32_t)val);
        break;
    }
    case 2: {
        uint32_t hi = (uint32_t)(val / 10000ULL);
        uint32_t lo = (uint32_t)(val % 10000ULL);
        int sig = fastio__emit_lead_fwd(dst, hi);
        memcpy(dst + sig, &fastio__lut2[lo], 4);
        total_len = sig + 4;
        break;
    }
    case 3: {
        uint64_t hi64 = val / 100000000ULL;
        uint64_t rem = val % 100000000ULL;
        uint32_t b1 = (uint32_t)(rem / 10000ULL);
        uint32_t b2 = (uint32_t)(rem % 10000ULL);
        int sig = fastio__emit_lead_fwd(dst, (uint32_t)hi64);
        memcpy(dst + sig, &fastio__lut2[b1], 4);
        memcpy(dst + sig + 4, &fastio__lut2[b2], 4);
        total_len = sig + 8;
        break;
    }
    case 4: {
        uint64_t hi64 = val / 1000000000000ULL;
        uint64_t rem = val % 1000000000000ULL;
        uint32_t b1 = (uint32_t)(rem / 100000000ULL);
        rem %= 100000000ULL;
        uint32_t b2 = (uint32_t)(rem / 10000ULL);
        uint32_t b3 = (uint32_t)(rem % 10000ULL);
        int sig = fastio__emit_lead_fwd(dst, (uint32_t)hi64);
        memcpy(dst + sig, &fastio__lut2[b1], 4);
        memcpy(dst + sig + 4, &fastio__lut2[b2], 4);
        memcpy(dst + sig + 8, &fastio__lut2[b3], 4);
        total_len = sig + 12;
        break;
    }
    default: {
        uint64_t hi64 = val / 10000000000000000ULL;
        uint64_t rem = val % 10000000000000000ULL;
        uint32_t b1 = (uint32_t)(rem / 1000000000000ULL);
        rem %= 1000000000000ULL;
        uint32_t b2 = (uint32_t)(rem / 100000000ULL);
        rem %= 100000000ULL;
        uint32_t b3 = (uint32_t)(rem / 10000ULL);
        uint32_t b4 = (uint32_t)(rem % 10000ULL);
        int sig = fastio__emit_lead_fwd(dst, (uint32_t)hi64);
        memcpy(dst + sig, &fastio__lut2[b1], 4);
        memcpy(dst + sig + 4, &fastio__lut2[b2], 4);
        memcpy(dst + sig + 8, &fastio__lut2[b3], 4);
        memcpy(dst + sig + 12, &fastio__lut2[b4], 4);
        total_len = sig + 16;
        break;
    }
    }
    io->out.len += (size_t)total_len;
}

static inline void fastio_write_i64(FastIO *io, int64_t val) {
    if (val < 0) {
        fastio_write_char(io, '-');
        uint64_t u = (uint64_t)(-(val + 1)) + 1ULL;
        fastio_write_u64(io, u);
    } else {
        fastio_write_u64(io, (uint64_t)val);
    }
}

static inline void fastio_write_i32(FastIO *io, int32_t val) {
    if (val < 0) {
        fastio_write_char(io, '-');
        uint32_t u = (uint32_t)(-(val + 1)) + 1u;
        fastio_write_u32(io, u);
    } else {
        fastio_write_u32(io, (uint32_t)val);
    }
}

static inline unsigned __int128 fastio__parse_udigits128(FastInput *__restrict__ in) {
    const char *p = in->ptr;
    const char *end = in->end;
    unsigned __int128 acc = 0;

    const __m256i lo_bound = _mm256_set1_epi8('0' - 1);
    const __m256i hi_bound = _mm256_set1_epi8('9' + 1);

    while (p + 32 <= end) {
        __m256i v = _mm256_loadu_si256((const __m256i *)p);
        __m256i ge = _mm256_cmpgt_epi8(v, lo_bound);
        __m256i le = _mm256_cmpgt_epi8(hi_bound, v);
        __m256i is_digit = _mm256_and_si256(ge, le);
        unsigned mask = (unsigned)_mm256_movemask_epi8(is_digit);

        if (mask == 0xFFFFFFFFu) {
            for (int k = 0; k < 32; k += 8) {
                uint64_t chunk;
                memcpy(&chunk, p + k, 8);
                acc = acc * 100000000ULL + fastio__parse8(chunk);
            }
            p += 32;
            continue;
        }

        unsigned non_digit = ~mask;
        int run = __builtin_ctz(non_digit);
        int k = 0;
        for (; k + 8 <= run; k += 8) {
            uint64_t chunk;
            memcpy(&chunk, p + k, 8);
            acc = acc * 100000000ULL + fastio__parse8(chunk);
        }
        for (; k < run; ++k) {
            acc = acc * 10 + (unsigned)(p[k] - '0');
        }
        p += run;
        in->ptr = p;
        return acc;
    }

    while (p < end) {
        unsigned char c = (unsigned char)*p;
        if (c < '0' || c > '9') break;
        acc = acc * 10 + (unsigned)(c - '0');
        ++p;
    }
    in->ptr = p;
    return acc;
}

static inline unsigned __int128 fastio_read_u128(FastIO *io) {
    fastio__skip_ws(&io->in);
    return fastio__parse_udigits128(&io->in);
}

static inline __int128 fastio_read_i128(FastIO *io) {
    fastio__skip_ws(&io->in);
    int neg = 0;
    if (io->in.ptr < io->in.end && *io->in.ptr == '-') {
        neg = 1;
        ++io->in.ptr;
    }
    unsigned __int128 u = fastio__parse_udigits128(&io->in);
    if (!neg) return (__int128)u;
    return -(__int128)(u - 1) - 1;
}

static inline int fastio__u128_to_buf(unsigned __int128 val, char *tmp_end) {
    char *p = tmp_end;
    while (val >= 10000) {
        unsigned idx = (unsigned)(val % 10000);
        val /= 10000;
        p -= 4;
        memcpy(p, &fastio__lut2[idx], 4);
    }
    uint32_t hi = (uint32_t)val;
    int sig = fastio__sig4(hi);
    uint32_t sv = fastio__lut1[hi] >> ((4 - sig) * 8);
    p -= sig;
    memcpy(p, &sv, (size_t)sig);
    return (int)(tmp_end - p);
}

static inline void fastio_write_u128(FastIO *io, unsigned __int128 val) {
    char tmp[48];
    int len = fastio__u128_to_buf(val, tmp + 48);
    fastio_write_str(io, tmp + 48 - len, (size_t)len);
}

static inline void fastio_write_i128(FastIO *io, __int128 val) {
    if (val < 0) {
        fastio_write_char(io, '-');
        unsigned __int128 u = (unsigned __int128)(-(val + 1)) + 1;
        fastio_write_u128(io, u);
    } else {
        fastio_write_u128(io, (unsigned __int128)val);
    }
}

int main(void) {

    FastIO io;

    fastio_init(&io, 0, 1); 
    int64_t n = fastio_read_u32(&io);
    fastio_write_u32(&io, ((n + 1) * n) >> 1);

    fastio_destroy(&io);

    return 0;
}