oj.uz

Submission #361530

# Submission time Handle Problem Language Result Execution time Memory
361530 2021-01-30T12:20:05 Z Sorting Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 37280 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;

const int INF = 1e9 + 3;
int d[303][303];

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)
        for(int j = 0; j < n; ++j)
            d[i][j] = (i == j) ? 0 : INF; 

    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j){
            int dist = min(abs(i - j), abs(n - j + i));
            if(dist <= k - 1){
                if(p[i] < p[j])
                    d[j][i] = 1;
                else
                    d[i][j] = 1;
            }
        }

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            for(int k = 0; k < n; ++k)
                d[j][k] = min(d[j][i] + d[i][k], d[j][k]);
}

int compare_plants(int x, int y) {
    if(d[x][y] == INF && d[y][x] == INF) 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:159:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     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 384 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 65 ms 4204 KB Output is correct
7 Runtime error 303 ms 37280 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
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 2 ms 492 KB Output is correct
6 Correct 1076 ms 1772 KB Output is correct
7 Execution timed out 4059 ms 10732 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
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 2 ms 492 KB Output is correct
6 Correct 1076 ms 1772 KB Output is correct
7 Execution timed out 4059 ms 10732 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
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 Execution timed out 4059 ms 6892 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.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 3 ms 620 KB Output is correct
7 Correct 45 ms 1644 KB Output is correct
8 Correct 46 ms 1644 KB Output is correct
9 Correct 46 ms 1644 KB Output is correct
10 Correct 49 ms 1772 KB Output is correct
11 Correct 46 ms 1644 KB Output is correct
12 Correct 50 ms 1772 KB Output is correct
13 Correct 46 ms 1644 KB Output is correct

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 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1075 ms 1644 KB Output isn't correct
6 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 384 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 65 ms 4204 KB Output is correct
7 Runtime error 303 ms 37280 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -