oj.uz

Submission #393493

# Submission time Handle Problem Language Result Execution time Memory
393493 2021-04-23T15:37:18 Z phathnv Comparing Plants (IOI20_plants) C++11
11 / 100
 4000 ms 17332 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 67 ms 4044 KB Output is correct
7 Correct 384 ms 5176 KB Output is correct
8 Correct 620 ms 17220 KB Output is correct
9 Correct 856 ms 17324 KB Output is correct
10 Correct 2872 ms 17212 KB Output is correct
11 Execution timed out 4067 ms 17332 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 4 ms 436 KB Output is correct
7 Correct 84 ms 3700 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 89 ms 3652 KB Output is correct
11 Correct 1306 ms 3592 KB Output is correct
12 Execution timed out 4082 ms 3200 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 4 ms 436 KB Output is correct
7 Correct 84 ms 3700 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 89 ms 3652 KB Output is correct
11 Correct 1306 ms 3592 KB Output is correct
12 Execution timed out 4082 ms 3200 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 783 ms 3500 KB Output is correct
4 Execution timed out 4073 ms 16184 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 24 ms 1292 KB Output is correct
8 Correct 17 ms 1280 KB Output is correct
9 Correct 42 ms 1220 KB Output is correct
10 Correct 18 ms 1228 KB Output is correct
11 Correct 26 ms 1220 KB Output is correct
12 Correct 26 ms 1156 KB Output is correct
13 Correct 16 ms 1164 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 1041 ms 16564 KB Output is correct
7 Correct 2007 ms 16772 KB Output is correct
8 Correct 1012 ms 16952 KB Output is correct
9 Correct 1058 ms 17212 KB Output is correct
10 Execution timed out 4056 ms 16616 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 67 ms 4044 KB Output is correct
7 Correct 384 ms 5176 KB Output is correct
8 Correct 620 ms 17220 KB Output is correct
9 Correct 856 ms 17324 KB Output is correct
10 Correct 2872 ms 17212 KB Output is correct
11 Execution timed out 4067 ms 17332 KB Time limit exceeded
12 Halted 0 ms 0 KB -