結果

問題 No.59 鉄道の旅
コンテスト
ユーザー Unbakedbread
提出日時 2025-12-29 19:20:07
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 58 ms / 5,000 ms
コード長 919 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,218 ms
コンパイル使用メモリ 283,332 KB
実行使用メモリ 30,728 KB
最終ジャッジ日時 2025-12-29 19:20:12
合計ジャッジ時間 4,880 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template<typename T> 
struct fenwick_tree{
    int N; vector<T> v;
    fenwick_tree(int n):N(n),v(n,0){}
    void add(int i,T x){for(int t=i;t<N;t|=(t+1))v[t]+=x;}
    T sum(int l,int r){return _sum(r)-_sum(l);}
    T _sum(int i){T ans=0;for(int t=i;t>0;t&=(t-1))ans+=v[t-1];return ans;}
};

int main(void) {
	int N, K;
	cin >> N >> K;
	vector<int> W(N);
	for(int i = 0; i < N; ++i) cin >> W[i];
	
	vector<vector<pair<int, bool>>> v(1010101);
	for(int i = 0; i < N; ++i) v[abs(W[i])].emplace_back(make_pair(i, W[i] > 0));
	
	fenwick_tree<int> fw(N);
	for(int w = 1e6; w >= 1; --w) if(!v[w].empty()) {
		int cnt = 0;
		for(auto [i, sgn] : v[w]) {
			if(sgn) {
				if(fw.sum(0, i) < K) {
					++cnt;
					fw.add(i, 1);
				}
			}
			else {
				if(cnt) {
					--cnt;
					fw.add(i, -1);
				}
			}
		}
	}
	
	cout << fw.sum(0, N) << "\n";
	
	return 0;
}
0