結果
問題 | No.2055 12x34... |
ユーザー | Jashinchan |
提出日時 | 2022-08-23 23:57:27 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 9,671 bytes |
コンパイル時間 | 1,344 ms |
コンパイル使用メモリ | 65,000 KB |
実行使用メモリ | 21,068 KB |
最終ジャッジ日時 | 2024-10-11 06:18:46 |
合計ジャッジ時間 | 3,250 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 7 ms
19,400 KB |
testcase_01 | AC | 6 ms
19,392 KB |
testcase_02 | AC | 8 ms
19,784 KB |
testcase_03 | AC | 9 ms
20,292 KB |
testcase_04 | AC | 9 ms
20,676 KB |
testcase_05 | AC | 10 ms
20,680 KB |
testcase_06 | AC | 10 ms
20,544 KB |
testcase_07 | AC | 9 ms
20,292 KB |
testcase_08 | AC | 8 ms
20,164 KB |
testcase_09 | AC | 11 ms
20,940 KB |
testcase_10 | AC | 10 ms
20,932 KB |
testcase_11 | AC | 9 ms
20,044 KB |
testcase_12 | AC | 13 ms
20,168 KB |
testcase_13 | AC | 19 ms
20,680 KB |
testcase_14 | AC | 12 ms
19,916 KB |
testcase_15 | AC | 11 ms
20,044 KB |
testcase_16 | AC | 19 ms
20,800 KB |
testcase_17 | AC | 11 ms
20,040 KB |
testcase_18 | AC | 14 ms
20,548 KB |
testcase_19 | AC | 9 ms
19,656 KB |
testcase_20 | AC | 8 ms
19,392 KB |
testcase_21 | AC | 9 ms
19,784 KB |
testcase_22 | AC | 17 ms
21,068 KB |
testcase_23 | AC | 19 ms
20,928 KB |
testcase_24 | AC | 20 ms
20,932 KB |
testcase_25 | AC | 18 ms
20,932 KB |
testcase_26 | AC | 19 ms
20,936 KB |
testcase_27 | AC | 20 ms
20,932 KB |
testcase_28 | AC | 19 ms
20,932 KB |
testcase_29 | AC | 19 ms
20,928 KB |
testcase_30 | AC | 19 ms
20,940 KB |
testcase_31 | AC | 20 ms
20,940 KB |
testcase_32 | AC | 21 ms
20,932 KB |
testcase_33 | AC | 11 ms
20,940 KB |
testcase_34 | AC | 11 ms
20,800 KB |
testcase_35 | AC | 11 ms
20,928 KB |
testcase_36 | AC | 11 ms
20,932 KB |
testcase_37 | AC | 12 ms
20,936 KB |
testcase_38 | AC | 12 ms
21,056 KB |
testcase_39 | AC | 12 ms
20,940 KB |
testcase_40 | AC | 11 ms
20,936 KB |
testcase_41 | AC | 12 ms
20,932 KB |
testcase_42 | AC | 12 ms
21,060 KB |
コンパイルメッセージ
main.cpp:6: warning: "_GNU_SOURCE" redefined 6 | #define _GNU_SOURCE | <command-line>: note: this is the location of the previous definition
ソースコード
// clang-format off #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define _GNU_SOURCE #include <stdbool.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <math.h> #include <string.h> #include <time.h> typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef __int128_t i128; typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef __uint128_t u128; typedef float f32; typedef double f64; typedef long double f80; #define MIN(a, b) (((a) < (b)) ? (a) : (b)) #define MAX(a, b) (((a) > (b)) ? (a) : (b)) #define SWAP_REF(a, b) \ do { \ (a) ^= (b); \ (b) ^= (a); \ (a) ^= (b); \ } \ while(0); #define POPCNT32(a) ((a) ? __builtin_popcount((a)) : (0)) #define CTZ32(a) ((a) ? __builtin_ctz((a)) : 32) #define CLZ32(a) ((a) ? __builtin_clz((a)) : 32) #define POPCNT64(a) ((a) ? __builtin_popcountll((a)) : (0)) #define CTZ64(a) ((a) ? __builtin_ctzll((a)) : 64) #define CLZ64(a) ((a) ? __builtin_clzll((a)) : 64) #define MSB32(a) ((a) ? ((31) - __builtin_clz((a))) : (-1)) #define MSB64(a) ((a) ? ((63) - __builtin_clzll((a))) : (-1)) #define LSBit(a) ((a) & (-(a))) #define CLSBit(a) ((a) & ((a) - (1))) #define BIT_FLOOR32(a) ((a) ? (1u) << MSB32((a)) : (0)) #define BIT_FLOOR64(a) ((a) ? (1ull) << MSB64((a)) : (0)) #define BIT_CEIL32_REF(a) \ do { \ --(a); \ (a) |= (a) >> (1); \ (a) |= (a) >> (2); \ (a) |= (a) >> (4); \ (a) |= (a) >> (8); \ (a) |= (a) >> (16); \ (a)++; \ } while(0); #define BIT_CEIL64_REF(a) \ do { \ --(a); \ (a) |= (a) >> (1); \ (a) |= (a) >> (2); \ (a) |= (a) >> (4); \ (a) |= (a) >> (8); \ (a) |= (a) >> (16); \ (a) |= (a) >> (32); \ (a)++; \ } while(0); #define ROTL32_INNER(x, l) (((x) << (l)) | ((x) >> ((-l) & (31)))) #define ROTR32_INNER(x, r) (((x) >> (r)) | ((x) << ((-r) & (31)))) #define ROTR32(x, r) (((r) < (0)) ? (ROTL32_INNER((x), ((u64)(-r) % (32)))) : (ROTR32_INNER((x), ((r) % (32))))) #define ROTL32(x, l) ROTR32((x), (-l)) #define ROTL64_INNER(x, l) (((x) << (l)) | ((x) >> ((-l) & (63)))) #define ROTR64_INNER(x, r) (((x) >> (r)) | ((x) << ((-r) & (63)))) #define ROTR64(x, r) (((r) < (0)) ? (ROTL64_INNER((x), ((u64)(-r) % (64)))) : (ROTR64_INNER((x), ((r) % (64))))) #define ROTL64(x, l) ROTR64((x), (-l)) i32 in_i32(void) {/* -2147483648 ~ 2147483647 (> 10 ^ 9) */ i32 c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } static inline void out_i32_inner(i32 x) { if (x >= 10) out_i32_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void out_i32(i32 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i32_inner(x); } i64 in_i64(void) {/* -9223372036854775808 ~ 9223372036854775807 (> 10 ^ 18) */ i64 c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } static inline void out_i64_inner(i64 x) { if (x >= 10) out_i64_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void out_i64(i64 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i64_inner(x); } u32 in_u32(void) {/* 0 ~ 4294967295 (> 10 ^ 9) */ u32 c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; } void out_u32(u32 x) { if (x >= 10) out_u32(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } u64 in_u64(void) {/* 0 ~ 18446744073709551615 (> 10 ^ 19) */ u64 c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; } void out_u64(u64 x) { if (x >= 10) out_u64(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void NL(void) { putchar_unlocked('\n'); } void SP(void) { putchar_unlocked(' '); } void dump_int(int x) { fprintf(stderr, "\033[1;36m%d\033[0m\n", x); } void dump_i64(i64 x) { fprintf(stderr, "\033[1;36m%ld\033[0m\n", x); } void dump_u32(u32 x) { fprintf(stderr, "\033[1;36m%u\033[0m\n", x); } void dump_u64(u64 x) { fprintf(stderr, "\033[1;36m%lu\033[0m\n", x); } void dump_int_array(int *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%d\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%d\033[0m ", a[i]); } } } void dump_i64_array(i64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%ld\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%ld\033[0m ", a[i]); } } } void dump_u32_array(u32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%u\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%u\033[0m ", a[i]); } } } void dump_u64_array(u64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%lu\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%lu\033[0m ", a[i]); } } } void dump_int_array_range(int *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%d\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%d\033[0m ", a[i]); } } } void dump_i64_array_range(i64 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%ld\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%ld\033[0m ", a[i]); } } } void dump_u32_array_range(u32 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%u\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%u\033[0m ", a[i]); } } } void dump_u64_array_range(u64 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%lu\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%lu\033[0m ", a[i]); } } } void printb_32bit(u32 v) { u32 mask = (u32)1 << (sizeof(v) * CHAR_BIT - 1); do { putchar_unlocked(mask & v ? '1' : '0'); } while (mask >>= 1); } void printb_64bit(u64 v) { u64 mask = (u64)1 << (sizeof(v) * CHAR_BIT - 1); do { putchar_unlocked(mask & v ? '1' : '0'); } while (mask >>= 1); } // clang-format on #define BIT_SIZE 1048576 #define BIT_ARRAY 16384 u64 bitset[BIT_ARRAY] = {0}; void set(int i) { bitset[i / 64] |= (1ULL << (i % 64)); } void reset(int i) { bitset[i / 64] &= ~(1ULL << (i % 64)); } int test(int i) { return (bitset[i / 64] & (1ULL << (i % 64))) == 0 ? 0 : 1; } int count(void) { int ret = 0; for (int i = 0; i < BIT_ARRAY; ++i) { ret += __builtin_popcountll(bitset[i]); } return ret; } void flip(void) { for (int i = 0; i < BIT_ARRAY; ++i) { bitset[i] = ~bitset[i]; } } void flip_at(int i) { bitset[i / 64] ^= (1ULL << (i % 64)); } int find_prev(int i) { if (i == 0) return -1; if (test(--i)) return i; size_t M = i / 64; u64 buf = bitset[M]; buf &= (1ull << (i % 64)) - 1; if (buf != 0) return M * 64 + 63 - __builtin_clzll(buf); while (M--) { if (bitset[M] != 0) { return M * 64 + 63 - __builtin_clzll(bitset[M]); } } return -1; } int find_next(int i) { ++i; if (i >= BIT_SIZE) return BIT_SIZE; size_t M = i / 64; u64 buf = bitset[M]; buf &= (~(u64)(0ul)) << (i % 64); if (buf != 0ul) return M * 64 + __builtin_ctzll(buf); for (; ++M < BIT_ARRAY;) { if (bitset[M] != 0) return M * 64 + __builtin_ctzll(bitset[M]); } return BIT_SIZE; } u64 m_keys[BIT_SIZE] = {0}; u64 m_vals[BIT_SIZE] = {0}; u64 r = 0xa67840e8390ed557ull; void init(void) { memset(bitset, 0, BIT_ARRAY * sizeof(u64)); memset(m_keys, 0, BIT_SIZE * sizeof(u64)); memset(m_vals, 0, BIT_SIZE * sizeof(u64)); } static inline u32 hash(const u64 a) { return (u32)((a * r) >> 44); } u64 get_value(u64 key) { for (u32 i = hash(key);; ++i, i &= 1048575) { if (test(i) == 0) return 0; if (m_keys[i] == key) return m_vals[i]; } } void set_key(u64 key, u64 value) { for (u32 i = hash(key);; ++i, i &= 1048575) { if (test(i) == 0) { set(i); m_keys[i] = key; m_vals[i] = value; return; } if (m_keys[i] == key) { m_vals[i] = value; return; } } } int main(void) { init(); int T = in_i32(); u64 A[200000]; for (int i = 0; i < T; ++i) { A[i] = in_u64(); } int ans = 0; for (int i = 0; i < T; ++i) { u64 x = get_value(A[i] - 1); ans += x; ans %= 998244353; u64 y = get_value(A[i]); set_key(A[i], (y + x + 1) % 998244353); } out_i32(ans); NL(); return 0; }