Submission #361533

#	Time	Username	Problem	Language	Result	Execution time	Memory
361533		Sorting	Comparing Plants (IOI20_plants)	C++17	15 / 100	952 ms	18924 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 3;

int r_arr[N], p[N], k, n;

struct Segment_Tree{
    struct Node{
        int mn;
        array<int, 2> prev_zero;
    
        Node(){}
        Node(int mn, int i): mn(mn), prev_zero({i, 0}){}

        friend Node merge(const Node &l, const Node &r){
            Node ret;
            ret.mn = min(l.mn, r.mn);
            if(r.prev_zero[1] >= k) ret.prev_zero = r.prev_zero;
            else if(l.prev_zero[1]) ret.prev_zero = l.prev_zero;
            else ret.prev_zero = r.prev_zero;
            return ret;
        }
    };
    Node nd[4 * N];
    int lp[4 * N];

    void init(int i = 0, int l = 0, int r = n - 1){
        if(l == r){
            nd[i] = Node(r_arr[l], l);
            return;
        }

        int mid = (l + r) >> 1;
        init(2 * i + 1, l, mid);
        init(2 * i + 2, mid + 1, r);
        nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
    }

    void push(int i, int l, int r){
        nd[i].mn += lp[i];
        if(l != r){
            lp[2 * i + 1] += lp[i];
            lp[2 * i + 2] += lp[i];
        }
        lp[i] = 0;
    }

    int query(int i = 0, int l = 0, int r = n - 1){
        push(i, l, r);
        return nd[i].prev_zero[0];
    }

    int get_next_zero(int s, int i = 0, int l = 0, int r = n - 1){
        if(l > r) return n;

        push(i, l, r);
        if(r < s || nd[i].mn) return n;
        if(l == r) return l;

        int mid = (l + r) >> 1;
        int l_val = get_next_zero(s, 2 * i + 1, l, mid);
        if(l_val != n) return l_val;
        return get_next_zero(s, 2 * i + 2, mid + 1, r);
    }

    int get_prev_zero(int s, int i = 0, int l = 0, int r = n - 1){
        if(l > r) return -1;

        push(i, l, r);
        if(l > s || nd[i].mn) return -1;
        if(l == r) return l;

        int mid = (l + r) >> 1;
        int r_val = get_prev_zero(s, 2 * i + 2, mid + 1, r);
        if(r_val != -1) return r_val;
        return get_prev_zero(s, 2 * i + 1, l, mid);
    }

    void update_prev_zero(int s, int i = 0, int l = 0, int r = n - 1){
        if(l > r) return;

        push(i, l, r);
        if(l > s || r < s) return;
        if(l == r){
            nd[i].prev_zero = {s, s - get_prev_zero(s - 1, 0, 0, n - 1)};
            return;
        }

        int mid = (l + r) >> 1;
        update_prev_zero(s, 2 * i + 1, l, mid);
        update_prev_zero(s, 2 * i + 2, mid + 1, r);

        nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
    }

    void update_zeroes(int l2, int r2, int i = 0, int l = 0, int r = n - 1){
        if(l > r) return;

        push(i, l, r);
        if(nd[i].mn) return;
        if(r < l2 || r2 < l) return;
        if(l == r){
            update_prev_zero(l, i, l, r);
            return;
        }

        int mid = (l + r) >> 1;
        update_zeroes(l2, r2, 2 * i + 1, l, mid);
        update_zeroes(l2, r2, 2 * i + 2, mid + 1, r);

        nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
    }

    void change_value(int s, int val, int i = 0, int l = 0, int r = n - 1){
        if(l > r) return;

        push(i, l, r);
        if(r < s || s < l) return;
        if(l == r){
            nd[i] = Node(val, s);
            return;
        }

        int mid = (l + r) >> 1;
        change_value(s, val, 2 * i + 1, l, mid);
        change_value(s, val, 2 * i + 2, mid + 1, r);

        nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
    }

    void update(int l2, int r2, int val, int i = 0, int l = 0, int r = n - 1){
        if(l > r) return;

        push(i, l, r);
        if(r < l2 || r2 < l) return;
        if(l2 <= l && r <= r2){
            lp[i]+=val;
            push(i, l, r);
            return;
        }

        int mid = (l + r) >> 1;
        update(l2, r2, val, 2 * i + 1, l, mid);
        update(l2, r2, val, 2 * i + 2, mid + 1, r);

        nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
    }
} st;

struct Fenwick{
    int a[N];

    Fenwick(){}

    void clear(){
        fill(a, a + N, 0);
    }

    void update(int i, int v){
        for(++i; i < N; i+=i&-i)
            a[i] += v;
    }

    int query(int i){
        int ans = 0;
        for(++i; i >= 1; i-=i&-i)
            ans += a[i];
        return ans;
    }

    int query(int l, int r){
        return query(r) - query(l - 1);
    }
} f;

bool dp[2][N];
int rev_p[N];

void do_i(int i, bool which){
    int idx = rev_p[i];
    int sum = 0;
    sum += f.query(idx + 1, min(idx + k - 1, n - 1));
    if(idx + k - 1 > n - 1) sum += f.query(0, idx + k - n - 1);
    sum += f.query(max(idx - k + 1, 0), idx - 1);
    if(idx - k + 1 < 0) sum += f.query(n + idx - k + 1, n - 1);

    if(sum){
        dp[which][idx] = 1;
        f.update(idx, 1);
    }
}

void init(int _k, vector<int> _r) {
	k = _k;
    n = _r.size();
    for(int i = 0; i < _r.size(); ++i)
        r_arr[i] = _r[i];

    st.init();
    st.update_zeroes(0, n - 1);
    for(int i = n - 1; i >= 0; --i){
        int idx = st.query();
        p[idx] = i;
        //cout << idx << " idx" << endl;
        
        st.change_value(idx, n);
        if(idx){
            st.update(max(idx - (k - 1), 0), idx - 1, -1);
            st.update_zeroes(max(idx - (k - 1), 0), idx - 1);
        }
        if(idx < k - 1){
            st.update(n - ((k - 1) - idx), n - 1, -1);
            st.update_zeroes(n - ((k - 1) - idx), n - 1);
        }

        int nxt = st.get_next_zero(idx + 1);
        if(nxt != n) st.update_prev_zero(nxt);
    }

    for(int i = 0; i < n; ++i)
        rev_p[p[i]] = i;

    int x = p[0];
    f.update(0, 1);
    dp[0][0] = 1;
    for(int i = x + 1; i < n; ++i)
        do_i(i, 0);

    f.clear();
    f.update(0, 1);
    dp[1][0] = 1;
    for(int i = x - 1; i >= 0; --i)
        do_i(i, 1);
}

int compare_plants(int x, int y) {
    if(!dp[p[x] > p[y]][y]) return 0;
    return (p[x] > p[y]) ? 1 : -1;
}
/*
4 3 2
0 1 1 2
0 2
1 2
*/
/*
4 2 2
0 1 0 1
0 3
1 3
*/
/*
4 3 2
1 1 0 2
0 1
0 2
*/

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:199:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |     for(int i = 0; i < _r.size(); ++i)
      |                    ~~^~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 15 / 15
• Subtask 7: 0 / 25