oj.uz

Submission #361533

# Submission time Handle Problem Language Result Execution time Memory
361533 2021-01-30T12:43:10 Z Sorting Comparing Plants (IOI20_plants) C++17
15 / 100
 952 ms 18924 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Incorrect 1 ms 1132 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Incorrect 1 ms 1132 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Incorrect 1 ms 1132 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Incorrect 2 ms 1132 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 3 ms 1132 KB Output is correct
6 Correct 709 ms 17772 KB Output is correct
7 Correct 879 ms 18336 KB Output is correct
8 Correct 950 ms 18540 KB Output is correct
9 Correct 952 ms 18924 KB Output is correct
10 Correct 655 ms 17836 KB Output is correct
11 Correct 726 ms 18860 KB Output is correct
12 Correct 541 ms 18028 KB Output is correct
13 Correct 688 ms 18096 KB Output is correct
14 Correct 832 ms 18412 KB Output is correct
15 Correct 921 ms 18540 KB Output is correct
16 Correct 619 ms 18028 KB Output is correct
17 Correct 688 ms 18156 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Incorrect 1 ms 1132 KB Output isn't correct
4 Halted 0 ms 0 KB -