結果
問題 | No.469 区間加算と一致検索の問題 |
ユーザー |
![]() |
提出日時 | 2019-08-11 20:50:15 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 191 ms / 5,000 ms |
コード長 | 1,744 bytes |
コンパイル時間 | 481 ms |
コンパイル使用メモリ | 31,232 KB |
実行使用メモリ | 150,228 KB |
最終ジャッジ日時 | 2024-09-14 00:58:24 |
合計ジャッジ時間 | 8,538 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
コンパイルメッセージ
main.c: In function 'in': main.c:10:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration] 10 | #define gc() getchar_unlocked() | ^~~~~~~~~~~~~~~~ main.c:18:24: note: in expansion of macro 'gc' 18 | int n = 0, c = gc(); | ^~ main.c: In function 'out': main.c:11:15: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration] 11 | #define pc(c) putchar_unlocked(c) | ^~~~~~~~~~~~~~~~ main.c:31:17: note: in expansion of macro 'pc' 31 | if (!n) pc('0'); | ^~
ソースコード
// yukicoder: No.469 区間加算と一致検索の問題// bal4u 2019.8.11#include <stdio.h>typedef unsigned long long ll;//// 入出力関係#if 1#define gc() getchar_unlocked()#define pc(c) putchar_unlocked(c)#else#define gc() getchar()#define pc(c) putchar(c)#endifint in() { // 整数の入力int n = 0, c = gc();if (c == '-') { c = gc();do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');return -n;}do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');return n;}void out(int n) { // 非負整数の表示(出力)int i;char b[20];if (!n) pc('0');else {i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;while (i--) pc(b[i]);}pc('\n');}//// ハッシュ関数#define HASHSIZ 9999991typedef struct { ll s; int id; } HASH;HASH hash[HASHSIZ+5], *hashend = hash + HASHSIZ;int lookup(ll s) {HASH *p = hash + (int)(s % HASHSIZ);while (p->s) {if (p->s == s) return p->id;if (++p == hashend) p = hash;}return -1;}void insert(ll s, int id) {HASH *p = hash + (int)(s % HASHSIZ);while (p->s) {if (p->s == s) return;if (++p == hashend) p = hash;}p->s = s, p->id = id;}//// 疑似乱数発生unsigned xorshift() {static unsigned y = 2463534242;y = y ^ (y << 13), y = y ^ (y >> 17), y = y ^ (y << 5);return y;}ll phash[1000005];int main(){int i, N, Q, x; unsigned r;ll s;N = in(), Q = in();r = xorshift();phash[0] = 1; for (i = 1; i <= N; i++) phash[i] = phash[i - 1] * r;s = 0;insert(s+1, 0);for (i = 1; i <= Q; i++) {x = gc(), gc();if (x == '?') {x = lookup(s+1);out(x < 0? i: x);} else {int l = in(), r = in(), k = in();s += (ll)(phash[r] - phash[l]) * k;insert(s+1, i);}}return 0;}