Submission #238782

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
238782	2020-06-12T21:21:38 Z	Sorting	Santa Claus (RMI19_santa)	C++14	100 / 100	415 ms	14344 KB

santa

//fix zeros appearing before ones if the x is equal
#include <bits/stdc++.h>

using namespace std;

template<size_t k_N>
struct Segment_Tree{
    int nodes[4 * k_N], lazy[4 * k_N];
    static const int k_Inf = 1e9;

    Segment_Tree(){}

    void clear(){
        for(int i = 0; i < 4 * k_N; ++i){
            nodes[i] = 0;
            lazy[i] = 0;
        }
    }

    void update_lazy(int index, int l, int r){
        if(lazy[index]){
            if(l != r){
                lazy[2 * index + 1] += lazy[index];
                lazy[2 * index + 2] += lazy[index];
            }
            nodes[index] += lazy[index];
            lazy[index] = 0; 
        }
    }

    void update(int index, int l, int r, int sl, int sr, int value){
        update_lazy(index, l, r);
        if(sl > r || sr < l)
            return;
        if(sl <= l && r <= sr){
            lazy[index] += value;
            update_lazy(index, l, r);
            return;
        }

        int mid = (l + r) >> 1;
        update(2 * index + 1, l, mid, sl, sr, value);
        update(2 * index + 2, mid + 1, r, sl, sr, value);
    
        nodes[index] = min(nodes[2 * index + 1], nodes[2 * index + 2]);
    }

    int query(){
        update_lazy(0, 0, k_N - 1);
        return nodes[0];
    }
};

const int k_N = 1e5 + 7;

int n;
int x[k_N], v[k_N];
bool h[k_N];

Segment_Tree<k_N> st;
int answer[k_N];

void two_pointers(int start){
    for(int i = 0; i < start; ++i)
        answer[i] = -1;

    st.clear();
    for(int i = 0; i < start; ++i)
        st.update(0, 0, k_N - 1, v[i], k_N - 1, h[i] ? 1 : -1);

    set<pair<int, int>> s;
    int ptr = 0;
    for(int i = start; i <= n - 1; ++i){
        st.update(0, 0, k_N - 1, v[i], k_N - 1, h[i] ? 1 : -1);
        if(st.query() < 0){
            answer[i] = -1;
            continue;
        }

        while(ptr <= i){
            if(!h[ptr]){
                s.insert({v[ptr], ptr});
                ptr++;
            }
            else{
                auto it = s.upper_bound({v[ptr], -1});
                if(it == s.end()){
                    st.update(0, 0, k_N - 1, v[ptr], k_N - 1, -1);
                    if(st.query() < 0){
                        st.update(0, 0, k_N - 1, v[ptr], k_N - 1, 1);
                        break;
                    }
                    ptr++;
                    continue;
                }

                int index = it->second;
                st.update(0, 0, k_N - 1, v[index], k_N - 1, 1);
                st.update(0, 0, k_N - 1, v[ptr], k_N - 1, -1);

                if(st.query() < 0){
                    st.update(0, 0, k_N - 1, v[index], k_N - 1, -1);
                    st.update(0, 0, k_N - 1, v[ptr], k_N - 1, 1);
                    break;
                }

                ptr++;
                s.erase(it);
            }
        }

        if(ptr == i + 1)
            answer[i] = x[i];
        else
            answer[i] = 2 * x[i] - x[ptr];
    }

    for(int i = 0; i < n; ++i)
        cout << answer[i] << " ";
    cout << "\n";
}

int find_last_index(){
    int last_index = 0;
    for(int i = 0; i < n; ++i)
        if(!h[i])
            last_index = i;
    return last_index;
}

void read(){
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> x[i];
    for(int i = 0; i < n; ++i)
        cin >> h[i];
    for(int i = 0; i < n; ++i)
        cin >> v[i];
}

void solve_test(){
    read();
    int last_index = find_last_index();
    two_pointers(last_index);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--)
        solve_test();
}

Compilation message

santa.cpp: In instantiation of 'void Segment_Tree<k_N>::clear() [with long unsigned int k_N = 100007]':
santa.cpp:67:14:   required from here
santa.cpp:14:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < 4 * k_N; ++i){
                        ~~^~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	3456 KB	Output is correct
2	Correct	10 ms	3584 KB	Output is correct
3	Correct	19 ms	3712 KB	Output is correct
4	Correct	32 ms	4096 KB	Output is correct
5	Correct	56 ms	4608 KB	Output is correct
6	Correct	89 ms	5368 KB	Output is correct
7	Correct	152 ms	7160 KB	Output is correct
8	Correct	235 ms	9184 KB	Output is correct
9	Correct	286 ms	11256 KB	Output is correct
10	Correct	415 ms	14344 KB	Output is correct