結果

問題 No.59 鉄道の旅
ユーザー koprickykopricky
提出日時 2017-08-07 11:12:10
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 94 ms / 5,000 ms
コード長 2,846 bytes
コンパイル時間 2,275 ms
コンパイル使用メモリ 158,628 KB
実行使用メモリ 23,756 KB
最終ジャッジ日時 2023-08-02 03:03:51
合計ジャッジ時間 4,081 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
23,488 KB
testcase_01 AC 16 ms
23,436 KB
testcase_02 AC 16 ms
23,680 KB
testcase_03 AC 17 ms
23,312 KB
testcase_04 AC 94 ms
23,756 KB
testcase_05 AC 16 ms
23,304 KB
testcase_06 AC 16 ms
23,384 KB
testcase_07 AC 16 ms
23,432 KB
testcase_08 AC 26 ms
23,440 KB
testcase_09 AC 23 ms
23,672 KB
testcase_10 AC 24 ms
23,420 KB
testcase_11 AC 20 ms
23,492 KB
testcase_12 AC 55 ms
23,644 KB
testcase_13 AC 69 ms
23,696 KB
testcase_14 AC 81 ms
23,632 KB
testcase_15 AC 16 ms
23,412 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a, b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define show(x) cout <<#x<<" = "<<(x)<<endl
#define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 100005;

template<class V> class segtree {
private:
    int n,sz;
    vector<V> node, lazy;

public:
    segtree(vector<V> v) {
        sz = (int)v.size();
        n = 1;
        while(n < sz){
            n *= 2;
        }
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);
        rep(i,sz){
            node[i+n-1] = v[i];
        }
        for(int i=n-2; i>=0; i--){
            node[i] = node[i*2+1] + node[i*2+2];
        }
    }
    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }
    void range(int a, int b, V x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a){
            return;
        }
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            range(a, b, x, 2*k+1, l, (l+r)/2);
            range(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }
    V query(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a){
            return 0;
        }
        if(a <= l && r <= b){
            return node[k];
        }
        V vl = query(a, b, 2*k+1, l, (l+r)/2);
        V vr = query(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
    void print()
    {
        rep(i,sz){
            cout << query(i,i+1) << " ";
        }
        cout << endl;
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,K;
    cin >> n >> K;
    vector<int> vec(n,0);
    rep(i,n){
        cin >> vec[i];
    }
    segtree<int> st(vector<int>(1000000,0));
    rep(i,n){
        if(vec[i] > 0){
            int cnt = st.query(vec[i],1000001);
            if(cnt < K){
                st.range(vec[i],vec[i]+1,1);
            }
        }else{
            int cnt = st.query(-vec[i],-vec[i]+1);
            if(cnt){
                st.range(-vec[i],-vec[i]+1,-1);
            }
        }
    }
    cout << st.query(1,1000001) << endl;
    return 0;
}
0