結果
問題 | No.59 鉄道の旅 |
ユーザー |
![]() |
提出日時 | 2019-06-01 22:27:42 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 8 ms / 5,000 ms |
コード長 | 1,126 bytes |
コンパイル時間 | 986 ms |
コンパイル使用メモリ | 30,336 KB |
実行使用メモリ | 9,636 KB |
最終ジャッジ日時 | 2024-09-17 20:00:39 |
合計ジャッジ時間 | 1,437 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 12 |
コンパイルメッセージ
main.c: In function 'in': main.c:7:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration] 7 | #define gc() getchar_unlocked() | ^~~~~~~~~~~~~~~~ main.c:14:24: note: in expansion of macro 'gc' 14 | int n = 0, c = gc(); | ^~
ソースコード
// yukicoder: 59 鉄道の旅// 2019.6.1 bal4u#include <stdio.h>#if 1#define gc() getchar_unlocked()#else#define gc() getchar()#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;}#define MAXVAL 1000005int bit[MAXVAL], sz, p;void init(int maxVal) {sz = maxVal;p = 1; while (p < sz) p <<= 1;}void add(int i, int x) {i++; while (i <= sz)bit[i] += x, i += i & -i;}void insert(int val) { add(val, 1); }void erase(int val) { add(val, -1); }int nth_element(int n) {int a = 0, q = p; n--;while (q >>= 1)if (a+q <= sz && bit[a+q] <= n)a += q, n -= bit[a];return a;}int f[MAXVAL];int main(){int N, K, w, ans;N = in(), K = in(), ans = 0;init(MAXVAL);while (N--) {w = in();if (w > 0) {if (ans < K || nth_element(K) > MAXVAL-w)ans++, f[w]++, insert(MAXVAL-w);} else {w = -w;if (f[w] > 0) f[w]--, ans--, erase(MAXVAL-w);}}printf("%d\n", ans);return 0;}