oj.uz

Submission #434720

# Submission time Handle Problem Language Result Execution time Memory
434720 2021-06-21T15:36:57 Z yuto1115 Comparing Plants (IOI20_plants) C++17
55 / 100
 861 ms 11852 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

// min, arg_min
using S = pair<int, int>;

const S e = {inf, -1};

S op(const S &l, const S &r) {
    return (l.first <= r.first ? l : r);
}

using F = int;

const F id = 0;

F composition(const F &g, const F &f) {
    return g + f;
}

S mapping(const F &f, const S &x) {
    return S(x.first + f, x.second);
}

class lazy_segtree {
    int log, n;
    vector<S> d;
    vector<F> lazy;
    
    void update(int i) {
        assert(i < n);
        d[i] = op(d[2 * i], d[2 * i + 1]);
    }
    
    void all_apply(int i, const F &f) {
        d[i] = mapping(f, d[i]);
        if (i < n) lazy[i] = composition(f, lazy[i]);
    }
    
    void propagate(int i) {
        assert(i < n);
        all_apply(2 * i, lazy[i]);
        all_apply(2 * i + 1, lazy[i]);
        lazy[i] = id;
    }

public:
    lazy_segtree(const vector<S> &init) {
        log = 0;
        while ((1 << log) < init.size()) log++;
        n = 1 << log;
        d.assign(2 * n, e);
        rep(i, init.size()) d[n + i] = init[i];
        rrep(i, n) update(i);
        lazy.assign(n, id);
    }
    
    S prod(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) propagate(l >> i);
            if (((r >> i) << i) != r) propagate(r >> i);
        }
        S fl = e, fr = e;
        while (l < r) {
            if (l & 1) fl = op(fl, d[l++]);
            if (r & 1) fr = op(d[--r], fr);
            l >>= 1, r >>= 1;
        }
        return op(fl, fr);
    }
    
    void apply(int l, int r, const F &f) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) propagate(l >> i);
            if (((r >> i) << i) != r) propagate(r >> i);
        }
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1, r >>= 1;
            }
            l = l2, r = r2;
        }
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update(r >> i);
        }
    }
};

int k, n;
vi p;
vvi v;

void init(int _k, vi r) {
    k = _k;
    n = r.size();
    vector<S> init(n);
    rep(i, n) init[i] = {r[i], i};
    lazy_segtree st(init);
    set<int> can;
    auto get_min = [&](int i, int w) {
        if (i >= w) return st.prod(i - w, i);
        int rem = w - i;
        return op(st.prod(n - rem, n), st.prod(0, i));
    };
    auto dec = [&](int i) {
        if (i >= k - 1) {
            st.apply(i - k + 1, i, -1);
            return;
        }
        int rem = k - 1 - i;
        st.apply(n - rem, n, -1);
        st.apply(0, i, -1);
    };
    auto check = [&](int i) {
        S s = get_min(i, k - 1);
        if (s.first > 0) can.insert(i);
    };
    auto erase = [&](int i) {
        st.apply(i, i + 1, inf);
        dec(i);
        S s = get_min(i, k - 1);
        if (s.first == 0) check(s.second);
        s = get_min(i, n - 1);
        if (s.first == 0) check(s.second);
    };
    if (n <= 300) {
        v.resize(n);
        rep(i, n) {
            v[i].resize(n);
            st = lazy_segtree(init);
            can.clear();
            rep(j, n) if (!r[j]) check(j);
            while (true) {
                if (can.count(i)) can.erase(i);
                if (can.empty()) break;
                int nx = *can.begin();
                can.erase(nx);
                v[i][nx] = 1;
                erase(nx);
            }
        }
    } else {
        p.assign(n, -1);
        rep(i, n) if (!r[i]) check(i);
        rrep(t, n) {
            int nx = *can.begin();
            can.erase(nx);
            p[nx] = t;
            erase(nx);
        }
    }
}

int compare_plants(int x, int y) {
    if (n <= 300) {
        assert(v[x][y] or v[y][x]);
        if (v[x][y] and v[y][x]) return 0;
        return (v[x][y] ? -1 : 1);
    } else {
        return (p[x] > p[y] ? 1 : -1);
    }
}

Compilation message

plants.cpp: In constructor 'lazy_segtree::lazy_segtree(const std::vector<std::pair<int, int> >&)':
plants.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         while ((1 << log) < init.size()) log++;
      |                ~~~~~~~~~~~^~~~~~~~~~~~~

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 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 56 ms 3028 KB Output is correct
7 Incorrect 94 ms 3680 KB Output isn't correct
8 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 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 6 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 75 ms 3276 KB Output is correct
8 Correct 9 ms 332 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 82 ms 3396 KB Output is correct
11 Correct 70 ms 3276 KB Output is correct
12 Correct 67 ms 3524 KB Output is correct
13 Correct 77 ms 3280 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 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 6 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 75 ms 3276 KB Output is correct
8 Correct 9 ms 332 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 82 ms 3396 KB Output is correct
11 Correct 70 ms 3276 KB Output is correct
12 Correct 67 ms 3524 KB Output is correct
13 Correct 77 ms 3280 KB Output is correct
14 Correct 117 ms 3632 KB Output is correct
15 Correct 779 ms 11700 KB Output is correct
16 Correct 120 ms 3652 KB Output is correct
17 Correct 785 ms 11740 KB Output is correct
18 Correct 550 ms 11712 KB Output is correct
19 Correct 579 ms 11576 KB Output is correct
20 Correct 861 ms 11700 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 80 ms 3120 KB Output is correct
4 Correct 465 ms 11700 KB Output is correct
5 Correct 551 ms 11700 KB Output is correct
6 Correct 595 ms 11696 KB Output is correct
7 Correct 705 ms 11588 KB Output is correct
8 Correct 732 ms 11588 KB Output is correct
9 Correct 497 ms 11700 KB Output is correct
10 Correct 480 ms 11852 KB Output is correct
11 Correct 418 ms 11700 KB Output is correct
12 Correct 464 ms 11696 KB Output is correct
13 Correct 510 ms 11696 KB Output is correct

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 11 ms 400 KB Output is correct
7 Correct 114 ms 1276 KB Output is correct
8 Correct 73 ms 1320 KB Output is correct
9 Correct 76 ms 1288 KB Output is correct
10 Correct 84 ms 1264 KB Output is correct
11 Correct 93 ms 1220 KB Output is correct
12 Correct 80 ms 1280 KB Output is correct
13 Correct 83 ms 1300 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 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 2 ms 332 KB Output isn't correct
6 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 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 56 ms 3028 KB Output is correct
7 Incorrect 94 ms 3680 KB Output isn't correct
8 Halted 0 ms 0 KB -