Submission #1364849


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 push_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, lazy;
    int _size;  //the number of leaves
    T _init;
    
public:
    lazySegmentTree( vector<T> vec, T init = numeric_limits<T>::max() ): _init(init){
        if( vec.size()==0 )return ;
        
        _size = 1;
        while(_size<vec.size())_size*=2;
        dat.resize(_size*2);
        rep(i,vec.size())dat[i+_size] = vec[i];
        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*2] += lazy[num];
            lazy[num*2+1] += lazy[num];
        }
        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 dat[num];   //対象範囲外
        if(s<=l && r<=t){
//            lazy[num] += x * (r-l);
            lazy[num] += x;
            eval(num,l,r);
        }
        else{
            //            dat[num] = update(s, t, x, num*2, l, (l+r)/2) + update(s, t, x, num*2+1, (l+r)/2, r);
            dat[num] = max( update(s, t, x, num*2, l, (l+r)/2), update(s, t, x, num*2+1, (l+r)/2, r) );
        }
        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(vector<int>(MAX_T+1,0),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

Submission Time
Task D - 足ゲームII
User Yazaten
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2762 Byte
Status AC
Exec Time 214 ms
Memory 3456 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 34
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 2 ms 2688 KB
01-02.txt AC 2 ms 2688 KB
01-03.txt AC 2 ms 2688 KB
01-04.txt AC 5 ms 2688 KB
01-05.txt AC 213 ms 3456 KB
01-06.txt AC 214 ms 3456 KB
01-07.txt AC 214 ms 3456 KB
01-08.txt AC 214 ms 3456 KB
01-09.txt AC 213 ms 3456 KB
01-10.txt AC 3 ms 2688 KB
01-11.txt AC 214 ms 3456 KB
01-12.txt AC 213 ms 3456 KB
01-13.txt AC 213 ms 3456 KB
01-14.txt AC 214 ms 3456 KB
01-15.txt AC 7 ms 2688 KB
01-16.txt AC 213 ms 3456 KB
01-17.txt AC 213 ms 3456 KB
01-18.txt AC 213 ms 3456 KB
01-19.txt AC 213 ms 3456 KB
01-20.txt AC 7 ms 2688 KB
01-21.txt AC 210 ms 3456 KB
01-22.txt AC 210 ms 3456 KB
01-23.txt AC 211 ms 3456 KB
01-24.txt AC 166 ms 3456 KB
01-25.txt AC 2 ms 2688 KB
01-26.txt AC 2 ms 2688 KB
01-27.txt AC 131 ms 3456 KB
01-28.txt AC 132 ms 3456 KB
sample-01.txt AC 2 ms 2688 KB
sample-02.txt AC 2 ms 2688 KB
sample-03.txt AC 2 ms 2688 KB