結果
問題 | No.59 鉄道の旅 |
ユーザー | srjywrdnprkt |
提出日時 | 2022-12-20 02:51:46 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 41 ms / 5,000 ms |
コード長 | 1,371 bytes |
コンパイル時間 | 1,070 ms |
コンパイル使用メモリ | 106,944 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2023-08-11 10:11:48 |
合計ジャッジ時間 | 1,839 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
10,900 KB |
testcase_01 | AC | 6 ms
10,896 KB |
testcase_02 | AC | 4 ms
10,868 KB |
testcase_03 | AC | 5 ms
10,884 KB |
testcase_04 | AC | 40 ms
10,868 KB |
testcase_05 | AC | 5 ms
10,868 KB |
testcase_06 | AC | 4 ms
11,008 KB |
testcase_07 | AC | 5 ms
10,812 KB |
testcase_08 | AC | 8 ms
10,836 KB |
testcase_09 | AC | 9 ms
10,808 KB |
testcase_10 | AC | 8 ms
10,868 KB |
testcase_11 | AC | 6 ms
10,828 KB |
testcase_12 | AC | 19 ms
10,852 KB |
testcase_13 | AC | 41 ms
10,924 KB |
testcase_14 | AC | 38 ms
10,796 KB |
testcase_15 | AC | 5 ms
10,920 KB |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <map> #include <set> #include <iomanip> #include <queue> #include <algorithm> #include <numeric> #include <deque> #include <complex> using namespace std; //RSQ (0-indexed) template<class T> struct BIT { vector<T> bit; long long N; T P; BIT (long long n, T p = 0){ N = n; P = p; bit.resize(N); } void add(long long loc, T val){ loc++; while(loc <= N){ bit[loc-1] += val; if (P) bit[loc-1] %= P; loc += loc & -loc; } } long long sum(long long l, long long r){ T res = _sum(r) - _sum(l-1); if (P) res = (res + P) % P; return res; } long long _sum(long long r){ r++; T res = 0; while(r > 0){ res += bit[r-1]; if (P) res %= P; r -= r & -r; } return res; } }; int main(){ long long N, K, W, cnt; cin >> N >> K; BIT<long long> tree(1000001); for (int i=0; i<N; i++){ cin >> W; if (W > 0){ cnt = tree.sum(W, 1000000); if (cnt < K) tree.add(W, 1); } else{ W *= -1; if (tree.sum(W, W) > 0) tree.add(W, -1); } } cout << tree.sum(0, 1000000) << endl; return 0; }