結果
問題 | No.59 鉄道の旅 |
ユーザー | yuppe19 😺 |
提出日時 | 2019-03-07 14:04:09 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 19 ms / 5,000 ms |
コード長 | 1,194 bytes |
コンパイル時間 | 551 ms |
コンパイル使用メモリ | 69,228 KB |
実行使用メモリ | 7,376 KB |
最終ジャッジ日時 | 2023-09-05 19:24:44 |
合計ジャッジ時間 | 1,676 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,928 KB |
testcase_01 | AC | 3 ms
6,916 KB |
testcase_02 | AC | 3 ms
7,204 KB |
testcase_03 | AC | 4 ms
6,936 KB |
testcase_04 | AC | 19 ms
7,292 KB |
testcase_05 | AC | 4 ms
6,988 KB |
testcase_06 | AC | 3 ms
7,180 KB |
testcase_07 | AC | 4 ms
6,872 KB |
testcase_08 | AC | 5 ms
6,868 KB |
testcase_09 | AC | 5 ms
6,932 KB |
testcase_10 | AC | 5 ms
7,032 KB |
testcase_11 | AC | 4 ms
7,084 KB |
testcase_12 | AC | 12 ms
7,196 KB |
testcase_13 | AC | 17 ms
7,196 KB |
testcase_14 | AC | 17 ms
7,376 KB |
testcase_15 | AC | 3 ms
6,996 KB |
ソースコード
#include <iostream> #include <vector> using namespace std; using i64 = int64_t; template <class T> struct BIT { int N; vector<T> data; explicit BIT(int n); T sum(int k); // k 番目以下の総和 void add(int k, T val); }; // {{{ † BIT 実装 template <class T> BIT<T>::BIT(int n) { N = n + 1; data.assign(N, 0); } template <class T> T BIT<T>::sum(int k) { T res = 0; for(++k; k>0; k-=k&-k) { res += data[k]; } return res; } template <class T> void BIT<T>::add(int k, T x) { for(++k; k<N; k+=k&-k) { data[k] += x; } } // }}} int f(int n, int k, vector<int> &w) { constexpr int MAXI = 1'000'005; BIT<int> tree(MAXI+1); int cnt; for(int i=0; i<n; ++i) { if(w[i] > 0) { // w[i] 以上の個数を数える cnt = tree.sum(MAXI) - tree.sum(w[i]-1); if(cnt < k) { tree.add(w[i], 1); } } else { w[i] = -w[i]; cnt = tree.sum(w[i]) - tree.sum(w[i]-1); if(cnt) { tree.add(w[i], -1); } } } int res = tree.sum(MAXI); return res; } int main(void) { int N, K; scanf("%d%d", &N, &K); vector<int> W(N); for(int i=0; i<N; ++i) { scanf("%d", &W[i]); } int res = f(N, K, W); printf("%d\n", res); return 0; }