結果
問題 | No.674 n連勤 |
ユーザー | bal4u |
提出日時 | 2019-07-21 16:17:54 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 1,878 bytes |
コンパイル時間 | 444 ms |
コンパイル使用メモリ | 31,488 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-13 04:17:19 |
合計ジャッジ時間 | 2,095 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 7 ms
5,376 KB |
testcase_14 | AC | 7 ms
5,376 KB |
testcase_15 | AC | 6 ms
5,376 KB |
testcase_16 | AC | 30 ms
5,376 KB |
testcase_17 | AC | 30 ms
5,376 KB |
testcase_18 | AC | 9 ms
5,376 KB |
testcase_19 | AC | 7 ms
5,376 KB |
コンパイルメッセージ
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:19:17: note: in expansion of macro 'gc' 19 | int 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:33:21: note: in expansion of macro 'pc' 33 | while (i--) pc(b[i]); | ^~
ソースコード
// yukicoder: No.674 n連勤 // 2019.7.21 bal4u #include <stdio.h> #include <string.h> typedef long long ll; #if 1 #define gc() getchar_unlocked() #define pc(c) putchar_unlocked(c) #else #define gc() getchar() #define pc(c) putchar(c) #endif int in() { // 非負整数の入力 int n = 0; int c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } ll In() { // 非負整数の入力(long long対応) ll n = 0; int c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } void out(ll n) { // 正整数の表示(出力) int i; char b[50]; i = 0; while (n) b[i++] = n % 10 + '0', n /= 10; while (i--) pc(b[i]); pc('\n'); } const ll INF = 1000000000000000000LL+10; typedef struct { ll a, b; } T; T t[30003]; int sz; ll D, ans; // 二分探索。見つからなければ、一つ小さい要素を返す int bsch(int l, ll x) { int r = sz; while (l < r) { int m = (l+r) >> 1; if (t[m].a <= x) l = m + 1; else r = m; } return l-1; } void ma(int id) { ll w = t[id].b-t[id].a+1; if (w > ans) ans = w; } void del(int l, int r) { int i; if (l > r) return; for (i = r+1; i < sz; i++) memcpy(t+l++, t+i, sizeof(T)); sz = l; } void add(int l) { int i; for (i = sz; i > l; i--) memcpy(t+i, t+i-1, sizeof(T)); sz++; } void resolv(ll a, ll b) { int l = bsch(0, a), r = bsch(l, b); if (t[l].b+1 < a) { if (b+1 < t[l+1].a) { add(l++), t[l].a = a, t[l].b = b, ma(l); return; } t[++l].a = a; } if (b+1 == t[r+1].a) r++; if (b <= t[r].b) t[l].b = t[r].b; else if (b+1 < t[r+1].a) t[l].b = b; ma(l), del(l+1, r); } int main() { D = In(); int Q = in(); t[0].a = t[0].b = -2, t[1].a = t[1].b = INF, sz = 2; while (Q--) { ll a = In(), b = In(); resolv(a, b); out(ans); // int i; for (i = 0; i+1 < sz; i++) printf("(%lld,%lld) ", t[i].a, t[i].b); printf("\n"); } return 0; }