結果

問題 No.59 鉄道の旅
ユーザー togatogatogatoga
提出日時 2015-08-03 12:07:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 45 ms / 5,000 ms
コード長 2,103 bytes
コンパイル時間 713 ms
コンパイル使用メモリ 92,060 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-06-07 01:49:46
合計ジャッジ時間 1,562 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
11,136 KB
testcase_01 AC 7 ms
11,008 KB
testcase_02 AC 6 ms
10,880 KB
testcase_03 AC 7 ms
10,880 KB
testcase_04 AC 45 ms
10,880 KB
testcase_05 AC 7 ms
10,880 KB
testcase_06 AC 7 ms
11,136 KB
testcase_07 AC 7 ms
11,008 KB
testcase_08 AC 11 ms
11,136 KB
testcase_09 AC 11 ms
11,008 KB
testcase_10 AC 11 ms
11,008 KB
testcase_11 AC 9 ms
11,008 KB
testcase_12 AC 23 ms
10,880 KB
testcase_13 AC 42 ms
10,880 KB
testcase_14 AC 39 ms
11,008 KB
testcase_15 AC 7 ms
10,880 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <algorithm>
#include <functional>
#include <limits.h>
#include <bitset>

#include <tuple>
#include <unordered_map>

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int INF = 1 << 29;
const double EPS = 1e-9;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
// 0-indexed
//@verifiyed
// http://yukicoder.me/submissions/41347
///////////////////////////////////////////////////////////////////
template <typename Weight> class BIT {
private:
  int N;
  vector<Weight> data;

public:
  BIT() {}
  BIT(int N) : N(N) { data.resize(N + 1, 0); }
  void init(int N) {
    this->N = N;
    data.resize(N + 1, 0);
  }
  Weight sum(int index) { // O(logN) sum[0, index)
    Weight res = 0;
    for (--index; index >= 0; index = (index & (index + 1)) - 1) {
      res += data[index];
    }
    return res;
  }
  Weight sum(int left, int right) { // sum[left, right)
    return sum(right) - sum(left);
  }
  // add x to index
  void add(int index, Weight x) {
    for (; index < N; index |= (index + 1)) {
      data[index] += x;
    }
  }
  Weight operator[](int index) { // return array[index] 0-indexed
    return sum(index + 1) - sum(index);
  }
};
///////////////////////////////////////////////////////
int N, K;
const int MAX_W = 1000010;

int main() {
  cin >> N >> K;
  BIT<ll> bit;
  bit.init(MAX_W);

  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    if (x >= 0) {
      int res = bit.sum(x, MAX_W);
      if (res >= K) {
        continue;
      }
      bit.add(x, 1);
    } else {
      x = -x;
      int res = bit[x];
      if (res == 0)
        continue;
      bit.add(x, -1);
    }
  }
  cout << bit.sum(MAX_W) << endl;
  return 0;
}
0