oj.uz

답안 #72056

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72056 2018-08-26T05:01:12 Z cat > /dev/null(#2231, lobo_prix, jms100300, enochjung) 박스런 (FXCUP3_box) C++17
0 / 100
 4 ms 1052 KB 
#include<bits/stdc++.h>
using namespace std;
template<typename T>    
struct IT {    
    typedef size_t sint;    
    typedef function<T(const T&,const T&)> func;    
    T *arr;    
    T init_val;  

    sint N;    
    func F;    

    IT(sint n, func F):F(F) {    
        for (N = 1; N < n; N <<= 1);    
        arr = new T[N << 1]();    
        init_val = T();  
    }    

    IT(sint n, func F, T init_val):F(F),init_val(init_val) {  
        for (N = 1; N < n; N <<= 1);  
        arr = new T[N << 1];  
        fill(arr, arr + (N<<1), init_val);  
    }  

    void update(sint i, T val) {    
        i |= N;    
        arr[i] = val;    
        while (i >>= 1)    
            arr[i] = F(arr[i<<1], arr[i<<1 | 1]);    
    }    

    T query(sint l, sint r) {    
        l |= N, r |= N;    
        T lval = init_val, rval = init_val;    
        while (l <= r) {    
            if (l & 1)    
                lval = F(lval, arr[l++]);    
            if (!(r & 1))    
                rval = F(arr[r--], rval);    
            l >>= 1, r >>= 1;    
        }    
        return F(lval, rval);    
    }    
};  

const int MAX_N = 1e5;
map<int, int> valcomp;
int arr[MAX_N];
int res[MAX_N];

int main(void) {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    vector<int> vals;

    int N;  cin >> N;
    for (int i = 0; i < N; i ++) {
        cin >> arr[i];
        vals.push_back(arr[i]);
    }

    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int cur_idx = 0;
    for (int val : vals)
        valcomp[val] = cur_idx++;

    IT<int> segtree(cur_idx+1, [](const int& a, const int& b) { return max(a,b); }, -1);
    int last = 0;

    memset(res, -1, sizeof res);
    segtree.update(valcomp[arr[0]], 0);
    for (int i = 1; i < N; i ++) {
        int qidx = segtree.query(valcomp[arr[i]]+1, cur_idx);
        if (qidx != -1) {
            for (int k = qidx+1; k < i-last; k ++) 
                res[i-k-1] = k+1;

            last = max(last, i-qidx-1);
        }
        else {
            for (; last < i; last ++)
                res[last] = i-last;
        }
        segtree.update(valcomp[arr[i]], i);
    }

    for (int i = 0; i < N; i ++)
        cout << res[i] << ' ';
    cout << endl;
}

Compilation message

box.cpp: In instantiation of 'IT<T>::IT(IT<T>::sint, IT<T>::func, T) [with T = int; IT<T>::sint = long unsigned int; IT<T>::func = std::function<int(const int&, const int&)>]':
box.cpp:67:87:   required from here
box.cpp:11:10: warning: 'IT<int>::F' will be initialized after [-Wreorder]
     func F;
          ^
box.cpp:8:7: warning:   'int IT<int>::init_val' [-Wreorder]
     T init_val;
       ^~~~~~~~
box.cpp:19:5: warning:   when initialized here [-Wreorder]
     IT(sint n, func F, T init_val):F(F),init_val(init_val) {
     ^~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 816 KB Output is correct
4 Correct 4 ms 892 KB Output is correct
5 Incorrect 2 ms 1052 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 816 KB Output is correct
4 Correct 4 ms 892 KB Output is correct
5 Incorrect 2 ms 1052 KB Output isn't correct
6 Halted 0 ms 0 KB -