Submission #1515499

---

Source Code Expand

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

// 区間加算、区間最大のstarrysky木
struct starrysky {
  int n;
  const int init_ = 0;
  VI lazym, lazya;
  starrysky(){}
  starrysky(int n_) {init(n_);}
  void init(int n_) {
    n = 1; while(n<n_) n *= 2;
    lazym.assign(2*n-1, init_);
    lazya.assign(2*n-1, 0);
  }
  void add(int a, int b, int x) {add(a, b, x, 0, 0, n);}
  void add(int a, int b, int x, int k, int l, int r) {
    if(r <= a || b <= l) return;
    if(a <= l && r <= b) lazya[k] += x;
    else {
      add(a, b, x, k*2+1, l, (l+r)/2);
      add(a, b, x, k*2+2, (l+r)/2, r);
      // cout << "k:" << k << " " << lazym[k*2+1] << " " << lazya[k*2+1] << " " <<   lazym[k*2+2] << " " << lazya[k+2+2] << endl;
      lazym[k] = max(lazym[k*2+1]+lazya[k*2+1],
                      lazym[k*2+2]+lazya[k*2+2]);
    }
  }
  int query(int a, int b) {return query(a, b, 0, 0, n);}
  int query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return init_;
    if(a <= l && r <= b) return lazym[k] + lazya[k];
    int vl = query(a, b, k*2+1, l, (l+r)/2),
        vr = query(a, b, k*2+2, (l+r)/2, r);
    return max(vl, vr)+lazya[k];
  }
  void debug() {
    int num = 1, nn = 0;
    REP(i, 2*n-1) {
      cout << lazym[i] << "," << lazya[i] << " ";
      if(i == nn) {cout << endl; num *= 2; nn += num;}
    }
  }
};

starrysky seg(10000);
int s[100010], t[100010];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) {
    cin >> s[i] >> t[i];
    --s[i], --t[i];
    seg.add(s[i], t[i], 1);
    // seg.debug();
  }
  int ma = seg.query(0, seg.n), l = -1, r=-1;
  REP(i, 10000) {
    if(seg.query(i, i+1) == ma) {
      if(l == -1) l = i;
      r = i;
    }
  }
  // cout << ma << " " << l << " " << r << endl;
  REP(i, n) {
    if(l <= s[i] && t[i] <= r) {
      cout << ma-1 << endl;
      return 0;
    }
  }
  cout << ma << endl;

  return 0;
}

Submission Info

Judge Result