結果
問題 | No.59 鉄道の旅 |
ユーザー | tottoripaper |
提出日時 | 2014-12-08 21:57:17 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 61 ms / 5,000 ms |
コード長 | 1,393 bytes |
コンパイル時間 | 256 ms |
コンパイル使用メモリ | 27,636 KB |
実行使用メモリ | 13,268 KB |
最終ジャッジ日時 | 2023-08-26 05:34:09 |
合計ジャッジ時間 | 1,400 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
13,252 KB |
testcase_01 | AC | 5 ms
13,236 KB |
testcase_02 | AC | 5 ms
13,240 KB |
testcase_03 | AC | 5 ms
13,252 KB |
testcase_04 | AC | 61 ms
13,244 KB |
testcase_05 | AC | 5 ms
13,256 KB |
testcase_06 | AC | 5 ms
13,212 KB |
testcase_07 | AC | 6 ms
13,252 KB |
testcase_08 | AC | 12 ms
13,268 KB |
testcase_09 | AC | 10 ms
13,244 KB |
testcase_10 | AC | 11 ms
13,212 KB |
testcase_11 | AC | 8 ms
13,252 KB |
testcase_12 | AC | 38 ms
13,252 KB |
testcase_13 | AC | 42 ms
13,220 KB |
testcase_14 | AC | 52 ms
13,248 KB |
testcase_15 | AC | 6 ms
13,256 KB |
ソースコード
#include <cstdio> #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,j) FOR(i,0,j) const int MAX_N = 1000001; class SegmentTree{ public: SegmentTree(){} SegmentTree(int n){init(n);} void init(int n){ size = 1; while(size < n){ size *= 2; } REP(i, size*2-1){ data[i] = 0; } } void update(int k, int v){ k += size - 1; data[k] = v; while(k > 0){ k = (k-1) / 2; data[k] = data[k*2+1] + data[k*2+2]; } } int query(int l, int r){ return _query(l, r, 0, 0, size); } private: int _query(int a, int b, int k, int l, int r){ if(b <= l || r <= a){return 0;} if(a <= l && r <= b){return data[k];} return _query(a, b, 2*k+1, l, (l+r)/2) + _query(a, b, 2*k+2, (l+r)/2, r); } int data[MAX_N*4], size; }; SegmentTree st(MAX_N); int main(){ int N, K; scanf("%d %d", &N, &K); for(int i=0;i<N;i++){ int w; scanf("%d", &w); if(w < 0 && 0 < st.query(-w, -w+1)){ st.update(-w, st.query(-w, -w+1) - 1); }else if(w > 0 && st.query(w, 1000001) < K){ st.update(w, st.query(w, w+1) + 1); } } printf("%d\n", st.query(0, 1000001)); }