제출 #393496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393496		phathnv	식물 비교 (IOI20_plants)	C++11	30 / 100	1452 ms	44120 KiB

plants

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25