test/aoj/dsl_5_a.test.cpp

View this file on GitHub
Last update: 2022-12-29 23:27:10+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_A

Depends on

src/dp/imos.hpp

Code

#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_A"

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

#include "../../src/dp/imos.hpp"

int main() {
  int n, t;
  cin >> n >> t;
  vector<ImosInterval<long long>> intervals(n);
  for (int i = 0; i < n; i++) {
    int l, r;
    cin >> l >> r;
    intervals[i] = {l, r, 1};
  }
  Imos<long long> imos(t, intervals);
  long long ans = 0;
  for (int i = 0; i < t; i++) {
    ans = max(ans, imos.get(i));
  }
  cout << ans << endl;
  return 0;
}

#line 1 "test/aoj/dsl_5_a.test.cpp"
#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_A"

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

#line 2 "src/dp/imos.hpp"

#line 4 "src/dp/imos.hpp"
using namespace std;

template <typename T> struct ImosInterval {
  // [l, r), l and r is 0-indexed.
  int l, r;
  T v;
};

template <typename T> struct Imos {
private:
  int n;
  vector<T> s;

public:
  Imos(int n, const vector<ImosInterval<T>> &intervals) : n(n) {
    s.resize(n + 1, 0);
    for (auto interval : intervals) {
      s[interval.l] += interval.v;
      s[interval.r] -= interval.v;
    }
    for (int i = 0; i < n; ++i) {
      s[i + 1] += s[i];
    }
  }

  // i is 0-indexed.
  T get(int i) { return s[i]; }
};
#line 8 "test/aoj/dsl_5_a.test.cpp"

int main() {
  int n, t;
  cin >> n >> t;
  vector<ImosInterval<long long>> intervals(n);
  for (int i = 0; i < n; i++) {
    int l, r;
    cin >> l >> r;
    intervals[i] = {l, r, 1};
  }
  Imos<long long> imos(t, intervals);
  long long ans = 0;
  for (int i = 0; i < t; i++) {
    ans = max(ans, imos.get(i));
  }
  cout << ans << endl;
  return 0;
}