oj.uz

Submission #360886

# Submission time Handle Problem Language Result Execution time Memory
360886 2021-01-28T07:28:12 Z Sorting Comparing Plants (IOI20_plants) C++17
44 / 100
 891 ms 17388 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;

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);
    }
}

int compare_plants(int x, int y) {
    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:156:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for(int i = 0; i < _r.size(); ++i)
      |                    ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 82 ms 5484 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 77 ms 5484 KB Output is correct
11 Correct 79 ms 5296 KB Output is correct
12 Correct 75 ms 5612 KB Output is correct
13 Correct 74 ms 5484 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 82 ms 5484 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 77 ms 5484 KB Output is correct
11 Correct 79 ms 5296 KB Output is correct
12 Correct 75 ms 5612 KB Output is correct
13 Correct 74 ms 5484 KB Output is correct
14 Correct 126 ms 6892 KB Output is correct
15 Correct 873 ms 16492 KB Output is correct
16 Correct 126 ms 6764 KB Output is correct
17 Correct 829 ms 16492 KB Output is correct
18 Correct 656 ms 16412 KB Output is correct
19 Correct 491 ms 16364 KB Output is correct
20 Correct 759 ms 16364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 69 ms 4972 KB Output is correct
4 Correct 534 ms 16364 KB Output is correct
5 Correct 689 ms 16492 KB Output is correct
6 Correct 819 ms 16492 KB Output is correct
7 Correct 891 ms 17388 KB Output is correct
8 Correct 853 ms 17260 KB Output is correct
9 Correct 630 ms 17004 KB Output is correct
10 Correct 636 ms 17152 KB Output is correct
11 Correct 511 ms 16876 KB Output is correct
12 Correct 434 ms 17132 KB Output is correct
13 Correct 613 ms 17132 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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