oj.uz

답안 #302091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
302091 2020-09-18T12:45:11 Z kevinsogo 식물 비교 (IOI20_plants) C++17
27 / 100
 1897 ms 136576 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int mod(int a, int n) {
    if ((a %= n) < 0) a += n;
    return a;
}

int n;
int dist(int i, int j) {
    return mod(j - i - 1, n) + 1;
}

struct MinTree {
    int i, j;
    int m, a = 0;
    MinTree *l, *r;
    MinTree(const vector<int>& v, int i, int j): i(i), j(j) {
        if (j - i == 1) {
            m = v[i];
            l = r = nullptr;
        } else {
            int k = i + j >> 1;
            l = new MinTree(v, i, k);
            r = new MinTree(v, k, j);
            m = min(l->m, r->m);
        }
    }

    void visit() {
        if (a) {
            m += a;
            if (l) l->a += a, r->a += a;
            a = 0;
        }
    }
    
    void inc(int I, int J, int A) {
        if (I <= i && j <= J) {
            a += A;
            visit();
        } else {
            visit();
            if (!(J <= i || j <= I)) {
                l->inc(I, J, A);
                r->inc(I, J, A);
                m = min(l->m, r->m);
            }
        }
    }

    void get0s(int I, int J, vector<int>& t) {
        visit();
        if (m > 0 || J <= i || j <= I) return;
        if (l) {
            l->get0s(I, J, t);
            r->get0s(I, J, t);
        } else {
            t.push_back(i);
        }
    }

    void rinc(int I, int J, int A) {
        while (I < j) {
            I += j - i;
            J += j - i;
        }
        while (i < I) {
            I -= j - i;
            J -= j - i;
            inc(I, J, A);
        }
    }

    void rget0s(int I, int J, vector<int>& t) {
        while (I < j) {
            I += j - i;
            J += j - i;
        }
        while (i < I) {
            I -= j - i;
            J -= j - i;
            get0s(I, J, t);
        }
    }
};

struct MaxTree {
    int i, j;
    pair<int,int> m;
    MaxTree *l, *r;
    MaxTree(int v, int i, int j): i(i), j(j), m(v, i) {
        if (j - i == 1) {
            l = r = nullptr;
        } else {
            int k = i + j >> 1;
            l = new MaxTree(v, i, k);
            r = new MaxTree(v, k, j);
        }
    }

    void write(int I, int v) {
        if (i <= I && I < j) {
            if (l) {
                l->write(I, v);
                r->write(I, v);
                m = std::max(l->m, r->m);
            } else {
                m = {v, i};
            }
        }
    }

    pair<int,int> max(int I, int J) {
        if (I <= i && j <= J) {
            return m;
        } else if (J <= i || j <= I) {
            return {-3, -3};
        } else {
            return std::max(l->max(I, J), r->max(I, J));
        }
    }

    pair<int,int> rmax(int I, int J) {
        while (I < j) {
            I += j - i;
            J += j - i;
        }
        pair<int,int> ans(-3, -3);
        while (i < I) {
            I -= j - i;
            J -= j - i;
            ans = std::max(ans, max(I, J));
        }
        return ans;
    }
};

struct TreeTree {
    int k;
    vector<vector<int>> anc;
    vector<ll> pard, dists;
    vector<int> depth, height, down, upp, upi, lg;
    vector<vector<int>> ups;
    TreeTree() {}
    TreeTree(const vector<int>& par, const vector<ll>& pard):
            pard(pard), dists(par.size()), depth(par.size()), height(par.size()),
            down(par.size(), -1), upp(par.size(), -1), upi(par.size(), -1), lg(par.size() + 1) {
        int n = par.size();
        for (k = 0; 1 << k <= n; k++);
        anc = vector<vector<int>>(k, vector<int>(n, -1));
        anc[0] = par;
        for (int kk = 0; kk < k - 1; kk++) {
            for (int i = 0; i < n; i++) {
                int j = anc[kk][i];
                anc[kk + 1][i] = anc[kk][j];
            }
        }

        vector<vector<int>> adj(n);
        vector<int> pre;
        for (int i = 0; i < n; i++) {
            if (par[i] == i) pre.push_back(i);
            if (par[i] != i) adj[par[i]].push_back(i);
        }

        for (int f = 0; f < pre.size(); f++) {
            int i = pre[f];
            for (int j : adj[i]) {
                depth[j] = depth[i] + 1;
                dists[j] = dists[i] + pard[j];
                pre.push_back(j);
            }
        }

        reverse(pre.begin(), pre.end());
        for (int i : pre) {
            if (down[i] != -1)
                height[i] = height[down[i]] + 1;
            else
                down[i] = i;
            if (par[i] != i && (down[par[i]] == -1 || height[down[par[i]]] < height[i]))
                down[par[i]] = i;
            down[i] = down[down[i]];
        }
        
        reverse(pre.begin(), pre.end());
        for (int s : pre) {
            if (upi[s] == -1) {
                int pi = ups.size();
                ups.emplace_back(1, down[s]);
                for (int it = 2*(height[s] + 1); it--;) {
                    ups.back().push_back(par[ups.back().back()]);
                }
                for (int idx = 0; idx < ups.back().size(); idx++) {
                    int i = ups.back()[idx];
                    if (upi[i] == -1) {
                        upi[i] = pi;
                        upp[i] = idx;
                    }
                }
            }
        }

        for (int i = 2; i < lg.size(); i++)
            lg[i] = lg[i >> 1] + 1;
    }

    vector<pair<int,ll>> walk_up(int i, ll d, int t, int ct = 1) {
        t = max(0, min(depth[i], t));
        d -= dists[i];
        if (t > 0) {
            int kk = lg[t];
            i = anc[kk][i];
            // i = ups[upi[i]][upp[i] + t - (1 << kk)]; // should be wrong!
        }
        d += dists[i];
        vector<pair<int,ll>> res;
        for (; ct--; d -= pard[i], i = anc[0][i]) res.emplace_back(i, d);
        return res;
    }
};


vector<ll> depths;
void _jumpify(vector<int>& par, vector<ll>& dist, int k, int i) {
    if (depths[i] == -1) {
        if (par[i] == i) {
            depths[i] = 0;
        } else {
            _jumpify(par, dist, k, par[i]);
            depths[i] = dist[i] + depths[par[i]];
            while (par[i] != par[par[i]] && i / k == par[i] / k) {
                dist[i] += dist[par[i]];
                par[i] = par[par[i]];
            }
        }
    }
}

void jumpify(vector<int>& par, vector<ll>& dist, int k) {
    depths = vector<ll>(par.size(), -1);
    for (int i = 0; i < par.size(); i++) _jumpify(par, dist, k, i);
}

vector<int> vals;
TreeTree rttree, lftree;
int k;
void init(int k, vector<int> r) {
    ::k = k;
    n = r.size();
    vals = vector<int>(n);

    MinTree curr(r, 0, n);
    vector<int> likod(n), harap(n);
    unordered_set<int> oks;

    vector<int> cands;
    for (int i = 0; i < n; i++) if (!r[i]) cands.push_back(i);
    for (int x2 = 0, x1 = cands.size() - 1; x2 < cands.size(); x1 = x2++) {
        int j1 = cands[x1], j2 = cands[x2];
        harap[j1] = j2;
        likod[j2] = j1;
        if (dist(j1, j2) >= k) oks.insert(j2);
    }
    
    for (int v = n; v--;) {
        int j = *oks.begin();
        int j1 = likod[j], j2 = harap[j];
        oks.erase(j);
        vals[j] = v;
        curr.inc(j, j + 1, n + 1);
        curr.rinc(j - k + 1, j, -1);

        vector<int> bagos;
        curr.rget0s(j - k + 1, j, bagos);

        if (v > 0) {
            if (j == j1 && j == j2) {
                j1 = bagos.back();
                j2 = bagos.front();
            }

            bagos.insert(bagos.begin(), j1);
            bagos.push_back(j2);
            for (int x1 = 0, x2 = 1; x2 < bagos.size(); x1++, x2++) {
                int j1 = bagos[x1], j2 = bagos[x2];
                harap[j1] = j2;
                likod[j2] = j1;
                if (dist(j1, j2) >= k) {
                    oks.insert(j2);
                } else if (oks.count(j2)) {
                    oks.erase(j2);
                }
            }
        }
    }

    vector<int> lfs(n, -1), rts(n, -1);
    MaxTree wals(-2, 0, n);
    vector<int> inds(n);
    for (int i = 0; i < n; i++) inds[vals[i]] = i;
    for (int x : inds) {
        wals.write(x, -1);
        int m;
        tie(m, lfs[x]) = wals.rmax(x - k + 1, x + 1);
        tie(m, rts[x]) = wals.rmax(x, x + k);
        wals.write(x, vals[x]);
    }

    vector<ll> lfdists(n), rtdists(n);
    for (int i = 0; i < n; i++) {
        lfdists[i] = dist(lfs[i], i);
        rtdists[i] = dist(i, rts[i]);
    }

    jumpify(lfs, lfdists, k);
    jumpify(rts, rtdists, k);

    lftree = TreeTree(lfs, lfdists);
    rttree = TreeTree(rts, rtdists);
}

bool is_fixed_right(int x, int y) {
    for (auto [X, rem] : rttree.walk_up(x, dist(x, y), dist(x, y) / k - 1, 4)) {
        if (abs(rem) < k && vals[X] >= vals[y]) return true;
    }
    return false;
}

bool is_fixed_left(int x, int y) {
    for (auto [X, rem] : lftree.walk_up(x, dist(y, x), dist(y, x) / k - 1, 4)) {
        if (abs(rem) < k && vals[X] >= vals[y]) return true;
    }
    return false;
}

int compare_plants(int x, int y) {
    int mul = 1;
    if (vals[x] < vals[y]) {
        swap(x, y);
        mul = -1;
    }

    return (is_fixed_right(x, y) || is_fixed_left(x, y)) * mul;
}

Compilation message

plants.cpp: In constructor 'MinTree::MinTree(const std::vector<int>&, int, int)':
plants.cpp:25:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |             int k = i + j >> 1;
      |                     ~~^~~
plants.cpp: In constructor 'MaxTree::MaxTree(int, int, int)':
plants.cpp:98:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |             int k = i + j >> 1;
      |                     ~~^~~
plants.cpp: In constructor 'TreeTree::TreeTree(const std::vector<int>&, const std::vector<long long int>&)':
plants.cpp:169:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         for (int f = 0; f < pre.size(); f++) {
      |                         ~~^~~~~~~~~~~~
plants.cpp:197:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |                 for (int idx = 0; idx < ups.back().size(); idx++) {
      |                                   ~~~~^~~~~~~~~~~~~~~~~~~
plants.cpp:207:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |         for (int i = 2; i < lg.size(); i++)
      |                         ~~^~~~~~~~~~~
plants.cpp: In function 'void jumpify(std::vector<int>&, std::vector<long long int>&, int)':
plants.cpp:245:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  245 |     for (int i = 0; i < par.size(); i++) _jumpify(par, dist, k, i);
      |                     ~~^~~~~~~~~~~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:262:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  262 |     for (int x2 = 0, x1 = cands.size() - 1; x2 < cands.size(); x1 = x2++) {
      |                                             ~~~^~~~~~~~~~~~~~
plants.cpp:288:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  288 |             for (int x1 = 0, x2 = 1; x2 < bagos.size(); x1++, x2++) {
      |                                      ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 124 ms 3192 KB Output is correct
7 Incorrect 204 ms 14076 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 9 ms 1024 KB Output is correct
7 Correct 135 ms 6368 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 128 ms 6136 KB Output is correct
11 Correct 135 ms 6264 KB Output is correct
12 Correct 145 ms 6136 KB Output is correct
13 Correct 125 ms 6392 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 9 ms 1024 KB Output is correct
7 Correct 135 ms 6368 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 128 ms 6136 KB Output is correct
11 Correct 135 ms 6264 KB Output is correct
12 Correct 145 ms 6136 KB Output is correct
13 Correct 125 ms 6392 KB Output is correct
14 Correct 248 ms 14708 KB Output is correct
15 Correct 1897 ms 123272 KB Output is correct
16 Correct 206 ms 14588 KB Output is correct
17 Correct 1756 ms 122756 KB Output is correct
18 Correct 877 ms 136576 KB Output is correct
19 Correct 888 ms 121724 KB Output is correct
20 Correct 1328 ms 129788 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 145 ms 4248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Incorrect 34 ms 1152 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Incorrect 1036 ms 118532 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 124 ms 3192 KB Output is correct
7 Incorrect 204 ms 14076 KB Output isn't correct
8 Halted 0 ms 0 KB -