Submission #1177263

---

Source Code Expand

#include <bits/stdc++.h>
 
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
 
struct S002 {
  int n;
  S002& operator > (long& x) {
    n = x;
    return *this;
  }
  S002& operator > (long&& x) {
    n = x;
    return *this;
  }
  S002& operator >= (long& x) {
    if( scanf("%ld", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (double& x) {
    if( scanf("%lf", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (std::string& s) {
    if( not (std::cin >> s) ) exit(0);
    return *this;
  }
  template<typename a>
  S002& operator >= (std::vector<a>& v) {
    v.resize(n);
    for(long i = 0; i < n; ++i) {
      *this >= v[i];
    }
    return *this;
  }
  template<typename a, std::size_t s>
  S002& operator >= (std::array<a, s>& x) {
    for(long i = 0; i < (long)s; ++i) {
      *this >= x[i];
    }
    return *this;
  }
};

template<typename a>
struct S001 {
  int n;
  std::vector<a> xs;
  S001(const std::vector<a>& ys) : xs(ys.size() + 1) {
    int n = (int)ys.size();
    a t = 0;
    xs[0] = 0;
    for(int i = 0; i < n; ++i) {
      t += ys[i];
      xs[i+1] = t;
    }
  }
  a operator [] (int i) {
    return xs[i];
  }
  a f(int x, int y) {
    return xs[y] - xs[x];
  }
  typename std::vector<a>::iterator begin() { return xs.begin(); }
  typename std::vector<a>::iterator end() { return xs.end(); }
};

template<typename a>
struct S024 {
  std::map<a, long> map;
  S024(const std::vector<a>& xs) {
    std::vector<a> ys = xs;
    std::sort(ys.begin(), ys.end());
    ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
    for(long i = 0; i < (long)ys.size(); ++i) {
      map[ys[i]] = i;
    }
  }
  long operator [] (a x) {
    return map[x];
  }
};

struct Solver {
  long n;
  std::vector<std::array<long, 2>> xs;
  Solver() {
    S002 reader;
    reader >= n >n>= xs;
  }
  void solve() {
    std::vector<long> ys;
    for(long i = 0; i < (long)xs.size(); ++i) {
      ys.push_back(xs[i][0]);
      ys.push_back(xs[i][1]);
    }
    S024<long> ws(ys);
    std::vector<long> ts(212345, 0);
    for(long i = 0; i < (long)xs.size(); ++i) {
      ts[ws[xs[i][0]]] += 1;
      ts[ws[xs[i][1]]+1] -= 1;
    }
    S001<long> ss(ts);
    long res = *std::max_element(ss.begin(), ss.end());
    printf("%ld\n", res);
  }
};
 
int main() {
  loop std::unique_ptr<Solver>(new Solver())->solve();
  return 0;
}

Submission Info

Judge Result