Submission #1370978


Source Code Expand

#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#define REP(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
template <class T> struct StarrySkyTreeMax {

    int N;
    vector<T> node_acc, node_max;
    const T INF = numeric_limits<T>::min() / 2;
  
    StarrySkyTreeMax (int n) {
        N = 2 << (int)log2(n);
        node_acc.resize(N*2,0);
        node_max.resize(N*2,0); 
    }

    void add(int l, int r, T val) {
        _add(l,r,val,0,0,N);
    }
    
    T get_max(int l, int r) {
        return _get_max(l,r,0,0,N);
    }

    void _add(int a, int b, T x, int k, int l, int r) {
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            node_acc[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);
            T l_val = node_max[k*2+1] + node_acc[k*2+1];
            T r_val = node_max[k*2+2] + node_acc[k*2+2];
            node_max[k] = max(l_val,r_val);
        }
    }

    T _get_max(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return INF;
        if (a <= l && r <= b) return node_max[k] + node_acc[k];
        T l_val = _get_max(a,b,k*2+1,l,(l+r)/2);
        T r_val = _get_max(a,b,k*2+2,(l+r)/2,r);
        return max(l_val,r_val) + node_acc[k];
    }

};

int main() {

    StarrySkyTreeMax<int> inst(100010);

    int N; cin >> N;
    vector<int> S(N),T(N);
    REP(i,N) cin >> S[i] >> T[i];

    REP(i,N) inst.add(S[i],T[i],1);

    int ans = 1e9;

    REP(i,N) {
        inst.add(S[i],T[i],-1);
        ans = min(ans,inst.get_max(0,N+1));
        inst.add(S[i],T[i],1);
    }

    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task D - 足ゲームII
User kosakkun
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1747 Byte
Status WA
Exec Time 179 ms
Memory 3072 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
WA × 1
AC × 25
WA × 9
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 WA 2 ms 2304 KB
01-02.txt WA 2 ms 2304 KB
01-03.txt WA 2 ms 2304 KB
01-04.txt WA 4 ms 2304 KB
01-05.txt AC 177 ms 3072 KB
01-06.txt AC 178 ms 3072 KB
01-07.txt AC 177 ms 3072 KB
01-08.txt AC 179 ms 3072 KB
01-09.txt AC 177 ms 3072 KB
01-10.txt WA 3 ms 2304 KB
01-11.txt AC 179 ms 3072 KB
01-12.txt AC 178 ms 3072 KB
01-13.txt AC 178 ms 3072 KB
01-14.txt AC 177 ms 3072 KB
01-15.txt WA 6 ms 2304 KB
01-16.txt AC 178 ms 3072 KB
01-17.txt AC 178 ms 3072 KB
01-18.txt AC 177 ms 3072 KB
01-19.txt AC 177 ms 3072 KB
01-20.txt WA 6 ms 2304 KB
01-21.txt AC 177 ms 3072 KB
01-22.txt AC 176 ms 3072 KB
01-23.txt AC 176 ms 3072 KB
01-24.txt AC 135 ms 3072 KB
01-25.txt AC 2 ms 2304 KB
01-26.txt AC 2 ms 2304 KB
01-27.txt AC 126 ms 3072 KB
01-28.txt AC 127 ms 3072 KB
sample-01.txt AC 2 ms 2304 KB
sample-02.txt AC 2 ms 2304 KB
sample-03.txt WA 2 ms 2304 KB