oj.uz

Submission #393022

# Submission time Handle Problem Language Result Execution time Memory
393022 2021-04-22T14:49:53 Z phathnv Comparing Plants (IOI20_plants) C++11
44 / 100
 693 ms 15668 KB 
#include <bits/stdc++.h>
#include "plants.h"

using namespace std;

int curVal;
vector<int> p;

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

void init(int k, vector<int> r) {
    int 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);
    }
	return;
}

int compare_plants(int x, int y) {
	if (p[x] > p[y])
        return 1;
    else
        return -1;
	return 0;
}

Compilation message

plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:111:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  111 |     else
      |     ^~~~
plants.cpp:113:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  113 |  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 Incorrect 1 ms 296 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 256 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 79 ms 5220 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 73 ms 5256 KB Output is correct
11 Correct 72 ms 5092 KB Output is correct
12 Correct 69 ms 5336 KB Output is correct
13 Correct 72 ms 5216 KB Output is correct

Subtask #3
13.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 256 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 79 ms 5220 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 73 ms 5256 KB Output is correct
11 Correct 72 ms 5092 KB Output is correct
12 Correct 69 ms 5336 KB Output is correct
13 Correct 72 ms 5216 KB Output is correct
14 Correct 108 ms 6176 KB Output is correct
15 Correct 626 ms 14932 KB Output is correct
16 Correct 106 ms 6128 KB Output is correct
17 Correct 594 ms 14988 KB Output is correct
18 Correct 530 ms 14564 KB Output is correct
19 Correct 524 ms 15048 KB Output is correct
20 Correct 693 ms 15048 KB Output is correct

Subtask #4
17.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 67 ms 3864 KB Output is correct
4 Correct 403 ms 15668 KB Output is correct
5 Correct 462 ms 14532 KB Output is correct
6 Correct 517 ms 14564 KB Output is correct
7 Correct 537 ms 14836 KB Output is correct
8 Correct 565 ms 14940 KB Output is correct
9 Correct 416 ms 14408 KB Output is correct
10 Correct 407 ms 14296 KB Output is correct
11 Correct 376 ms 14192 KB Output is correct
12 Correct 412 ms 14560 KB Output is correct
13 Correct 488 ms 14528 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 296 KB Output isn't correct
5 Halted 0 ms 0 KB -