結果
問題 | No.59 鉄道の旅 |
ユーザー |
![]() |
提出日時 | 2016-11-22 17:26:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,020 bytes |
コンパイル時間 | 2,107 ms |
コンパイル使用メモリ | 101,816 KB |
実行使用メモリ | 11,784 KB |
最終ジャッジ日時 | 2024-12-24 23:24:14 |
合計ジャッジ時間 | 1,986 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 8 WA * 4 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <queue>#include <stack>#include <map>#include <algorithm>#include <sstream>#include <cmath>#include <set>#include <iomanip>#include <deque>#include <stdio.h>using namespace std;#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)#define iREP(i,Itr) for(auto (i)=(Itr).begin();(i)!=(Itr).end();(i)++)#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())#define PB_VEC(Itr1,Itr2) (Itr1).insert((Itr1).end(),(Itr2).begin(),(Itr2).end())#define UNIQUE(Itr) sort((Itr).begin(),(Itr).end()); (Itr).erase(unique((Itr).begin(),(Itr).end()),(Itr).end())#define LBOUND(Itr,val) lower_bound((Itr).begin(),(Itr).end(),(val))#define UBOUND(Itr,val) upper_bound((Itr).begin(),(Itr).end(),(val))typedef long long ll;class BinaryIndexTree{public:vector<int> bit;int bit_size;BinaryIndexTree(int size){bit_size=size+1;bit.resize(size+1);for(int i=0;i<size+1;i++)bit[i]=0;}int sum(int i){int res=0;while(i>0){res+=bit[i];i-=i&-i;}return res;}void add(int i, int x){while(i<=bit_size){bit[i]+=x;i+=i&-i;}}};map<int,int> wcnt;int main(){BinaryIndexTree inst(1000010);int N,K; cin>>N>>K;REP(i,N){int w; cin>>w;if(w<0){if(wcnt.find(abs(w))!=wcnt.end()){wcnt[abs(w)]--;inst.add(abs(w),-1);}}else{int sum=inst.sum(1000010)-inst.sum(abs(w)-1);if(sum<K){if(wcnt.find(abs(w))!=wcnt.end()){wcnt[abs(w)]++;}else{wcnt[abs(w)]=1;}inst.add(abs(w),1);}}}cout<<inst.sum(1000010)<<endl;return 0;}