oj.uz

Submission #393496

# Submission time Handle Problem Language Result Execution time Memory
393496 2021-04-23T15:47:23 Z phathnv Comparing Plants (IOI20_plants) C++11
30 / 100
 1452 ms 44120 KB 
#include <bits/stdc++.h>
#include "plants.h"

using namespace std;

int curVal, n;
vector<int> p, Left[18], Right[18];

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);
    }
    for(int i = 0; i < 18; i++){
        Left[i].assign(n, -1);
        Right[i].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[0][p] = (x >= 0? ord[x] : p);
        Left[0][p] = dist(Left[0][p], p, n);
        x = -st.getMin((p + 1) % n, (p + k - 1) % n);
        Right[0][p] = (x >= 0? ord[x] : p);
        Right[0][p] = dist(p, Right[0][p], n);
        st.update(p, p, -1e9 - i);
    }
    for(int i = 1; i <= 17; i++)
        for(int u = 0; u < n; u++){
            Left[i][u] = Left[i - 1][u] + Left[i - 1][(u - Left[i - 1][u] % n + n) % n];
            Right[i][u] = Right[i - 1][u] + Right[i - 1][(u + Right[i - 1][u]) % n];
        }

	return;
}

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

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:144:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  144 |     for(int i = 1; i <= 17; i++)
      |     ^~~
plants.cpp:150:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  150 |  return;
      |  ^~~~~~
plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:177:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  177 |     if (Right[0][u] > 0 && p[u] > p[x])
      |     ^~
plants.cpp:179:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  179 |  return 0;
      |  ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 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 135 ms 3076 KB Output is correct
7 Correct 298 ms 6912 KB Output is correct
8 Correct 1452 ms 41084 KB Output is correct
9 Correct 1422 ms 41084 KB Output is correct
10 Correct 1426 ms 41032 KB Output is correct
11 Correct 1348 ms 41092 KB Output is correct
12 Correct 1355 ms 44120 KB Output is correct
13 Correct 1258 ms 44032 KB Output is correct
14 Correct 1338 ms 44096 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 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 7 ms 464 KB Output is correct
7 Correct 103 ms 4204 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 103 ms 4076 KB Output is correct
11 Correct 143 ms 3952 KB Output is correct
12 Correct 191 ms 4104 KB Output is correct
13 Correct 104 ms 4340 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 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 7 ms 464 KB Output is correct
7 Correct 103 ms 4204 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 103 ms 4076 KB Output is correct
11 Correct 143 ms 3952 KB Output is correct
12 Correct 191 ms 4104 KB Output is correct
13 Correct 104 ms 4340 KB Output is correct
14 Correct 177 ms 7200 KB Output is correct
15 Incorrect 1321 ms 41452 KB Output isn't correct
16 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 131 ms 3468 KB Output is correct
4 Correct 1258 ms 42696 KB Output is correct
5 Correct 1282 ms 41516 KB Output is correct
6 Correct 1335 ms 41380 KB Output is correct
7 Correct 1302 ms 41284 KB Output is correct
8 Incorrect 1306 ms 41324 KB Output isn't correct
9 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 208 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 35 ms 880 KB Output is correct
8 Correct 19 ms 900 KB Output is correct
9 Correct 28 ms 964 KB Output is correct
10 Correct 20 ms 900 KB Output is correct
11 Correct 34 ms 964 KB Output is correct
12 Correct 32 ms 964 KB Output is correct
13 Correct 19 ms 892 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 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 1185 ms 41092 KB Output is correct
7 Correct 1113 ms 41208 KB Output is correct
8 Correct 1020 ms 41088 KB Output is correct
9 Incorrect 1198 ms 41156 KB Output isn't correct
10 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 0 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 135 ms 3076 KB Output is correct
7 Correct 298 ms 6912 KB Output is correct
8 Correct 1452 ms 41084 KB Output is correct
9 Correct 1422 ms 41084 KB Output is correct
10 Correct 1426 ms 41032 KB Output is correct
11 Correct 1348 ms 41092 KB Output is correct
12 Correct 1355 ms 44120 KB Output is correct
13 Correct 1258 ms 44032 KB Output is correct
14 Correct 1338 ms 44096 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 7 ms 464 KB Output is correct
21 Correct 103 ms 4204 KB Output is correct
22 Correct 3 ms 332 KB Output is correct
23 Correct 5 ms 460 KB Output is correct
24 Correct 103 ms 4076 KB Output is correct
25 Correct 143 ms 3952 KB Output is correct
26 Correct 191 ms 4104 KB Output is correct
27 Correct 104 ms 4340 KB Output is correct
28 Correct 177 ms 7200 KB Output is correct
29 Incorrect 1321 ms 41452 KB Output isn't correct
30 Halted 0 ms 0 KB -