oj.uz

Submission #434728

# Submission time Handle Problem Language Result Execution time Memory
434728 2021-06-21T15:52:36 Z yuto1115 Comparing Plants (IOI20_plants) C++17
75 / 100
 1651 ms 18592 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 sum;
vi p;
vvi v;
vi to, rev;

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 (k <= 2) {
        sum.resize(n + 1);
        rep(i, n) sum[i + 1] = sum[i] + r[i];
    } else 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);
        }
        {
            to.resize(n);
            st = lazy_segtree(init);
            can.clear();
            rep(j, n) if (!r[j]) check(j);
            while (true) {
                if (can.count(0)) can.erase(0);
                if (can.empty()) break;
                int nx = *can.begin();
                can.erase(nx);
                to[nx] = 1;
                erase(nx);
            }
        }
        {
            rev.resize(n);
            rep(i, n) init[i] = {k - 1 - r[i], i};
            st = lazy_segtree(init);
            can.clear();
            rep(j, n) if (r[j] == k - 1) check(j);
            while (true) {
                if (can.count(0)) can.erase(0);
                if (can.empty()) break;
                int nx = *can.begin();
                can.erase(nx);
                rev[nx] = 1;
                erase(nx);
            }
        }
    }
}

int compare_plants(int x, int y) {
    if (k <= 2) {
        int s = 1;
        if (x > y) {
            swap(x, y);
            s = -1;
        }
        if (sum[y] - sum[x] == 0) return s;
        if (sum[y] - sum[x] == y - x) return -s;
        if (sum[x] - sum[0] + sum[n] - sum[y] == 0) return -s;
        if (sum[x] - sum[0] + sum[n] - sum[y] == x + n - y) return s;
        return 0;
    } else 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 if (x == 0) {
        assert(to[y] or rev[y]);
        if (to[y] and rev[y]) return 0;
        return (to[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
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 0 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 64 ms 3032 KB Output is correct
7 Correct 72 ms 3620 KB Output is correct
8 Correct 98 ms 11592 KB Output is correct
9 Correct 98 ms 11588 KB Output is correct
10 Correct 124 ms 11616 KB Output is correct
11 Correct 104 ms 11588 KB Output is correct
12 Correct 111 ms 11592 KB Output is correct
13 Correct 98 ms 11716 KB Output is correct
14 Correct 91 ms 11592 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 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 6 ms 332 KB Output is correct
7 Correct 86 ms 3400 KB Output is correct
8 Correct 7 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 87 ms 3432 KB Output is correct
11 Correct 86 ms 3264 KB Output is correct
12 Correct 97 ms 3504 KB Output is correct
13 Correct 87 ms 3488 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 6 ms 332 KB Output is correct
7 Correct 86 ms 3400 KB Output is correct
8 Correct 7 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 87 ms 3432 KB Output is correct
11 Correct 86 ms 3264 KB Output is correct
12 Correct 97 ms 3504 KB Output is correct
13 Correct 87 ms 3488 KB Output is correct
14 Correct 167 ms 4392 KB Output is correct
15 Correct 1408 ms 18368 KB Output is correct
16 Correct 199 ms 4412 KB Output is correct
17 Correct 1501 ms 18336 KB Output is correct
18 Correct 1084 ms 18372 KB Output is correct
19 Correct 1121 ms 18488 KB Output is correct
20 Correct 1651 ms 18376 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 69 ms 3168 KB Output is correct
4 Correct 919 ms 18388 KB Output is correct
5 Correct 1234 ms 18372 KB Output is correct
6 Correct 1174 ms 18432 KB Output is correct
7 Correct 1247 ms 18392 KB Output is correct
8 Correct 1469 ms 18336 KB Output is correct
9 Correct 1289 ms 18508 KB Output is correct
10 Correct 901 ms 18528 KB Output is correct
11 Correct 101 ms 11588 KB Output is correct
12 Correct 861 ms 18384 KB Output is correct
13 Correct 997 ms 18340 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 9 ms 332 KB Output is correct
7 Correct 101 ms 1232 KB Output is correct
8 Correct 77 ms 1332 KB Output is correct
9 Correct 76 ms 1220 KB Output is correct
10 Correct 75 ms 1252 KB Output is correct
11 Correct 94 ms 1272 KB Output is correct
12 Correct 79 ms 1260 KB Output is correct
13 Correct 96 ms 1212 KB Output is correct

Subtask #6
15.0 / 15.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 4 ms 360 KB Output is correct
6 Correct 1378 ms 18524 KB Output is correct
7 Correct 1285 ms 18440 KB Output is correct
8 Correct 1237 ms 18332 KB Output is correct
9 Correct 1403 ms 18384 KB Output is correct
10 Correct 1215 ms 18368 KB Output is correct
11 Correct 1185 ms 18468 KB Output is correct
12 Correct 919 ms 18360 KB Output is correct
13 Correct 1304 ms 18468 KB Output is correct
14 Correct 1107 ms 18368 KB Output is correct
15 Correct 1224 ms 18468 KB Output is correct
16 Correct 894 ms 18592 KB Output is correct
17 Correct 1198 ms 18416 KB Output is correct

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 0 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 64 ms 3032 KB Output is correct
7 Correct 72 ms 3620 KB Output is correct
8 Correct 98 ms 11592 KB Output is correct
9 Correct 98 ms 11588 KB Output is correct
10 Correct 124 ms 11616 KB Output is correct
11 Correct 104 ms 11588 KB Output is correct
12 Correct 111 ms 11592 KB Output is correct
13 Correct 98 ms 11716 KB Output is correct
14 Correct 91 ms 11592 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 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 6 ms 332 KB Output is correct
20 Correct 6 ms 332 KB Output is correct
21 Correct 86 ms 3400 KB Output is correct
22 Correct 7 ms 332 KB Output is correct
23 Correct 6 ms 332 KB Output is correct
24 Correct 87 ms 3432 KB Output is correct
25 Correct 86 ms 3264 KB Output is correct
26 Correct 97 ms 3504 KB Output is correct
27 Correct 87 ms 3488 KB Output is correct
28 Correct 167 ms 4392 KB Output is correct
29 Correct 1408 ms 18368 KB Output is correct
30 Correct 199 ms 4412 KB Output is correct
31 Correct 1501 ms 18336 KB Output is correct
32 Correct 1084 ms 18372 KB Output is correct
33 Correct 1121 ms 18488 KB Output is correct
34 Correct 1651 ms 18376 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 69 ms 3168 KB Output is correct
38 Correct 919 ms 18388 KB Output is correct
39 Correct 1234 ms 18372 KB Output is correct
40 Correct 1174 ms 18432 KB Output is correct
41 Correct 1247 ms 18392 KB Output is correct
42 Correct 1469 ms 18336 KB Output is correct
43 Correct 1289 ms 18508 KB Output is correct
44 Correct 901 ms 18528 KB Output is correct
45 Correct 101 ms 11588 KB Output is correct
46 Correct 861 ms 18384 KB Output is correct
47 Correct 997 ms 18340 KB Output is correct
48 Correct 1 ms 204 KB Output is correct
49 Correct 1 ms 204 KB Output is correct
50 Correct 1 ms 204 KB Output is correct
51 Correct 1 ms 204 KB Output is correct
52 Correct 1 ms 204 KB Output is correct
53 Correct 9 ms 332 KB Output is correct
54 Correct 101 ms 1232 KB Output is correct
55 Correct 77 ms 1332 KB Output is correct
56 Correct 76 ms 1220 KB Output is correct
57 Correct 75 ms 1252 KB Output is correct
58 Correct 94 ms 1272 KB Output is correct
59 Correct 79 ms 1260 KB Output is correct
60 Correct 96 ms 1212 KB Output is correct
61 Incorrect 68 ms 3312 KB Output isn't correct
62 Halted 0 ms 0 KB -