Submission #1359035

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)
//#define INF (1LL<<59)


//0-index 半開区間遅延セグツリー(値の加算) verified AOJ DSL_2_G, CODEFESTIVAL2015-D
template<class T>
class lazySegmentTree{
private:
    vector<T> dat;
    vector<T> lazy;
    int _size;  //the number of leaves
    T _init;
    
public:
    //    lazySegmentTree( vector<T> vec, T init = numeric_limits<T>::max() ): _init(init){
    //        int size = vec.size();
    //        if(size==0)return ;
    //
    //        _size = 1;
    //        while(_size<size)_size*=2;
    //        dat.resize(_size*2);
    //        rep(i,vec.size())dat[i+_size] = vec[i];
    //        lazy.resize(_size*2,_init);
    //    }
    
    lazySegmentTree( int size, T init = numeric_limits<T>::max() ): _init(init){
        if(size==0)return ;
        
        _size = 1;
        while(_size<size)_size*=2;
        
        dat.resize(_size*2,_init);
        lazy.resize(_size*2,_init);
    }
    
    
    void eval(int num, int l, int r){
        if(lazy[num]==0) return ;
        dat[num] += lazy[num];
        
        if(r-l>1){  //葉でない時
            lazy[num*2] += lazy[num]/2;
            lazy[num*2+1] += lazy[num]/2;
        }
        lazy[num] = 0;
    }
    
    
    
    T update(int s, int t, T x, int num=1, int l=0, int r=-1){
        if(r==-1)r =_size;
        
        eval(num,l,r);
        
        if(r<=s || t<=l) return _init ;   //対象範囲外
        //        if(s<=l && r<=t) lazy[num] += x * (r-l);
        if(s<=l && r<=t){
            lazy[num] += x * (r-l);
            eval(num,l,r);
        }
        else{
            update(s, t, x, num*2, l, (l+r)/2);
            update(s, t, x, num*2+1, (l+r)/2, r);
//            dat[num] = dat[num*2] + dat[num*2+1];   //和
            dat[num] = max( dat[num*2], dat[num*2+1] );   //最大値
        }
        return dat[num];
    }
    
    
    T find(int s, int t, int num=1, int l=0, int r=-1){
        if(r==-1)r = _size;
        
        eval(num,l,r);
        
        
        if(r<=s || t<=l) return _init;  //対象範囲外
        if(s<=l && r<=t) return dat[num];
        else{
//            return find(s, t, num*2, l, (l+r)/2) + find(s, t, num*2+1, (l+r)/2, r); //和
            return max( find(s, t, num*2, l, (l+r)/2), find(s, t, num*2+1, (l+r)/2, r) ); //最大値
        }
    }
    
    int size(){ return _size; }
};


#define MAX_T 100000
int main() {
    int n; cin >> n;
    vector<int> s(n), t(n);
    rep (i,n) cin >> s[i] >> t[i];
    lazySegmentTree<int> q(MAX_T+1,0);
    rep (i,n) q.update(s[i], t[i], 1);
    int result = 1000000007;
    rep (i,n) {
        q.update(s[i], t[i], -1);
        result = min(result, q.find(0, MAX_T+1));
        q.update(s[i], t[i], +1);
    }
    cout << result << endl;
    return 0;
}

Submission Info

Judge Result