Submission #393493

#	Time	Username	Problem	Language	Result	Execution time	Memory
393493		phathnv	Comparing Plants (IOI20_plants)	C++11	11 / 100	4082 ms	17332 KiB

plants

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

using namespace std;

int curVal, n;
vector<int> p, Left, Right;

struct SegmentTree{
    int n;
    vector<int> d, lazy;
    void build(int id, int l, int r, const vector<int> &a){
        if (l == r){
            d[id] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid, a);
        build(id << 1 | 1, mid + 1, r, a);
        d[id] = min(d[id << 1], d[id << 1 | 1]);
    }
    void init(const vector<int> &a){
        n = a.size();
        d.assign(n * 4 + 1, 0);
        lazy.assign(n * 4 + 1, 0);
        build(1, 0, n - 1, a);
    }
    void doLazy(int id, int l, int r){
        d[id] += lazy[id];
        if (l < r){
            lazy[id << 1] += lazy[id];
            lazy[id << 1 | 1] += lazy[id];
        }
        lazy[id] = 0;
        return;
    }
    void update(int id, int l, int r, int u, int v, int val){
        doLazy(id, l, r);
        if (v < l || r < u)
            return;
        if (u <= l && r <= v){
            lazy[id] += val;
            doLazy(id, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        d[id] = min(d[id << 1], d[id << 1 | 1]);
    }
    int getMin(int id, int l, int r, int u, int v){
        doLazy(id, l, r);
        if (v < l || r < u)
            return 1e9;
        if (u <= l && r <= v)
            return d[id];
        int mid = (l + r) >> 1;
        return min(getMin(id << 1, l, mid, u, v), getMin(id << 1 | 1, mid + 1, r, u, v));
    }
    int getMin(int l, int r){
        if (l <= r)
            return getMin(1, 0, n - 1, l, r);
        else
            return min(getMin(1, 0, n - 1, l, n - 1), getMin(1, 0, n - 1, 0, r));
    }
    void update(int l, int r, int val){
        if (l <= r){
            update(1, 0, n - 1, l, r, val);
        } else {
            update(1, 0, n - 1, l, n - 1, val);
            update(1, 0, n - 1, 0, r, val);
        }
    }
    int findPos0(int id, int l, int r, int u, int v){
        doLazy(id, l, r);
        if (v < l || r < u || d[id] > 0)
            return -1;
        if (l == r)
            return l;
        int mid = (l + r) >> 1;
        int res = findPos0(id << 1, l, mid, u, v);
        if (res == -1)
            res = findPos0(id << 1 | 1, mid + 1, r, u, v);
        return res;
    }
    int findPos0(int l, int r){
        if (l <= r)
            return findPos0(1, 0, n - 1, l, r);
        int res = findPos0(1, 0, n - 1, l, n - 1);
        if (res == -1)
            res = findPos0(1, 0, n - 1, 0, r);
        return res;
    }
} st;

void process(int pos, int n, int k){
    while (true){
        int nxt = st.findPos0((pos - k + 1 + n) % n, (pos - 1 + n) % n);
        if (nxt == -1)
            break;
        else
            process(nxt, n, k);
    }
    p[pos] = curVal--;
    st.update(pos, pos, 1e9);
    st.update((pos - k + 1 + n) % n, (pos - 1 + n) % n, -1);
}

int dist(int x, int y, int n){
    if (x <= y)
        return y - x;
    return n - x + y;
}

void init(int k, vector<int> r) {
    n = r.size();
    p.assign(n, -1);
    st.init(r);

    curVal = n - 1;
    while (curVal >= 0){
        int pos = st.findPos0(0, n - 1);
        assert(pos != -1);
        process(pos, n, k);
    }

    Left.assign(n, -1);
    Right.assign(n, -1);
    vector<int> ord(n);
    for(int i = 0; i < n; i++)
        ord[p[i]] = i;
    st.init(vector<int>(n, 1e9));
    for(int i = 0; i < n; i++){
        int p = ord[i];
        int x = -st.getMin((p - k + 1 + n) % n, (p - 1 + n) % n);
        Left[p] = (x >= 0? ord[x] : p);
        Left[p] = dist(Left[p], p, n);
        x = -st.getMin((p + 1) % n, (p + k - 1) % n);
        Right[p] = (x >= 0? ord[x] : p);
        Right[p] = dist(p, Right[p], n);
        st.update(p, p, -1e9 - i);
    }

	return;
}

int compare_plants(int x, int y) {
    int u;
    u = x;
    while (Left[u] && dist(u, x, n) + Left[u] < dist(y, x, n))
        u = (u - Left[u] + n) % n;
    if (Left[u] > 0 && p[u] > p[y])
        return 1;
    u = x;
    while (Right[u] && dist(x, u, n) + Right[u] < dist(x, y, n))
        u = (u + Right[u] + n) % n;
    if (Right[u] > 0 && p[u] > p[y])
        return 1;
    u = y;
    while (Left[u] && dist(u, y, n) + Left[u] < dist(x, y, n))
        u = (u - Left[u] + n) % n;
    if (Left[u] > 0 && p[u] > p[x])
        return -1;
    u = y;
    while (Right[u] && dist(y, u, n) + Right[u] < dist(y, x, n))
        u = (u + Right[u]) % n;
    if (Right[u] > 0 && p[u] > p[x])
        return -1;
	return 0;
}

Compilation message (stderr)

plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:167:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  167 |     if (Right[u] > 0 && p[u] > p[x])
      |     ^~
plants.cpp:169:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  169 |  return 0;
      |  ^~~~~~

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