結果

問題 No.59 鉄道の旅
ユーザー ytftytft
提出日時 2021-03-05 12:30:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 79 ms / 5,000 ms
コード長 2,173 bytes
コンパイル時間 1,661 ms
コンパイル使用メモリ 176,316 KB
実行使用メモリ 21,124 KB
最終ジャッジ日時 2024-10-06 09:50:24
合計ジャッジ時間 3,125 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<typename type>
vector<vector<type>> structure_segmenttree_create(vector<type> initial,function<type(type,type)> op,type unit){
    int n=initial.size();
    int expandedsize=1;
    int depth=1;
    while(expandedsize<n){
        expandedsize=expandedsize*2;
        depth++;
    }
    for(int i=n;i<expandedsize;i++){
        initial.push_back(unit);
    }
    vector<vector<type>> ret(depth);
    ret[0]=initial;
    for(int i=1;i<depth;i++){
        for(int j=0;j<ret[i-1].size();j+=2){
            ret[i].push_back(op(ret[i-1][j],ret[i-1][j+1]));
        }
    }
    return ret;
}

template<typename type>
void structure_segmenttree_update(vector<vector<type>>& tree,int index,type value,function<type(type,type)> op){
    tree[0][index]=value;
    for(int i=1;i<tree.size();i++){
        index=index/2;
        tree[i][index]=op(tree[i-1][index*2],tree[i-1][index*2+1]);
    }
}

template<typename type>
type structure_segmenttree_query(vector<vector<type>>& tree,int left,int right,function<type(type,type)> op,type unit,int depth=0){
    type answer=unit;
    if(left==right){
        return unit;
    }
    if(left%2==1){
        answer=tree[depth][left];
    }
    if(right%2==1){
        answer=op(answer,tree[depth][right-1]);
    }
    return op(answer,structure_segmenttree_query(tree,(left+1)/2,right/2,op,unit,depth+1));
}

int main(){
    int N,K;
    cin>>N>>K;
    vector<int> array(1000001);
    function<int(int,int)> add=[](int a,int b){return a+b;};
    vector<vector<int>> t=structure_segmenttree_create(array,add,0);
    int W;
    int num=0;
    int ans=0;
    for(int i=0;i<N;i++){
        cin>>W;
        if(W<0){
            W=-W;
            num=structure_segmenttree_query(t,W,W+1,add,0);
            if(num>0){
                structure_segmenttree_update(t,W,num-1,add);
                ans--;
            }
        }else{
            num=structure_segmenttree_query(t,W,W+1,add,0);
            if(structure_segmenttree_query(t,W,1000001,add,0)<K){
                structure_segmenttree_update(t,W,num+1,add);
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}
0