結果
問題 | No.59 鉄道の旅 |
ユーザー | imulan |
提出日時 | 2016-07-07 20:26:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 5,000 ms |
コード長 | 1,574 bytes |
コンパイル時間 | 1,914 ms |
コンパイル使用メモリ | 170,836 KB |
実行使用メモリ | 19,840 KB |
最終ジャッジ日時 | 2024-12-24 22:24:18 |
合計ジャッジ時間 | 3,123 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 15 ms
19,840 KB |
testcase_01 | AC | 15 ms
19,712 KB |
testcase_02 | AC | 15 ms
19,712 KB |
testcase_03 | AC | 16 ms
19,712 KB |
testcase_04 | AC | 62 ms
19,840 KB |
testcase_05 | AC | 15 ms
19,712 KB |
testcase_06 | AC | 15 ms
19,712 KB |
testcase_07 | AC | 15 ms
19,712 KB |
testcase_08 | AC | 22 ms
19,712 KB |
testcase_09 | AC | 20 ms
19,712 KB |
testcase_10 | AC | 20 ms
19,840 KB |
testcase_11 | AC | 18 ms
19,712 KB |
testcase_12 | AC | 46 ms
19,840 KB |
testcase_13 | AC | 41 ms
19,840 KB |
testcase_14 | AC | 50 ms
19,712 KB |
testcase_15 | AC | 15 ms
19,712 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define mp make_pair #define pb push_back #define fi first #define se second const int N=1000000; struct SumSegTree{ long n; vector<ll> dat; //初期化 SumSegTree(long _n){ n=1; while(n<_n) n*=2; dat=vector<ll>(2*n-1,0); } //k番目(0-indexed)の値に+a //負にはしない void update(long k, ll a){ k+=n-1; dat[k]=max(dat[k]+a,0LL); //更新 while(k>0){ k=(k-1)/2; dat[k]=dat[2*k+1]+dat[2*k+2]; } } //内部的に投げられるクエリ ll _query(long a, long b, long k, long l, long r){ if(r<=a || b<=l) return 0; if(a<=l && r<=b) return dat[k]; else{ ll vl=_query(a,b,2*k+1,l,(l+r)/2); ll vr=_query(a,b,2*k+2,(l+r)/2,r); return vl+vr; } } //[a,b)の和を求める ll query(long a, long b){ return _query(a,b,0,0,n); } }; int main() { int n,k; cin >>n >>k; SumSegTree st(N+2); rep(i,n) { int w; scanf(" %d", &w); if(w>0) { if(st.query(w,N+1)<k) st.update(w,1); } else { st.update(-w,-1); } //cout << st.query(0,N+1) << endl;; } cout << st.query(0,N+1) << endl;; return 0; }