oj.uz

Submission #434724

# Submission time Handle Problem Language Result Execution time Memory
434724 2021-06-21T15:43:40 Z yuto1115 Comparing Plants (IOI20_plants) C++17
70 / 100
 1460 ms 19064 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;
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 (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 (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
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 58 ms 2988 KB Output is correct
7 Incorrect 155 ms 4392 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 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 7 ms 332 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 84 ms 3452 KB Output is correct
8 Correct 7 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 83 ms 3420 KB Output is correct
11 Correct 76 ms 3404 KB Output is correct
12 Correct 78 ms 3648 KB Output is correct
13 Correct 83 ms 3440 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 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 7 ms 332 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 84 ms 3452 KB Output is correct
8 Correct 7 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 83 ms 3420 KB Output is correct
11 Correct 76 ms 3404 KB Output is correct
12 Correct 78 ms 3648 KB Output is correct
13 Correct 83 ms 3440 KB Output is correct
14 Correct 183 ms 4436 KB Output is correct
15 Correct 1408 ms 18336 KB Output is correct
16 Correct 183 ms 4412 KB Output is correct
17 Correct 1455 ms 18464 KB Output is correct
18 Correct 1022 ms 18340 KB Output is correct
19 Correct 1034 ms 18468 KB Output is correct
20 Correct 1460 ms 18400 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 75 ms 3168 KB Output is correct
4 Correct 906 ms 18424 KB Output is correct
5 Correct 1157 ms 18392 KB Output is correct
6 Correct 1125 ms 18372 KB Output is correct
7 Correct 1205 ms 18344 KB Output is correct
8 Correct 1456 ms 18340 KB Output is correct
9 Correct 1279 ms 18372 KB Output is correct
10 Correct 922 ms 18528 KB Output is correct
11 Correct 779 ms 18356 KB Output is correct
12 Correct 849 ms 18380 KB Output is correct
13 Correct 988 ms 18336 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 99 ms 1264 KB Output is correct
8 Correct 73 ms 1220 KB Output is correct
9 Correct 74 ms 1204 KB Output is correct
10 Correct 71 ms 1312 KB Output is correct
11 Correct 93 ms 1220 KB Output is correct
12 Correct 77 ms 1260 KB Output is correct
13 Correct 87 ms 1240 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 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 4 ms 296 KB Output is correct
6 Correct 1352 ms 18420 KB Output is correct
7 Correct 1202 ms 19064 KB Output is correct
8 Correct 1197 ms 18936 KB Output is correct
9 Correct 1388 ms 18976 KB Output is correct
10 Correct 1260 ms 18980 KB Output is correct
11 Correct 1157 ms 18976 KB Output is correct
12 Correct 944 ms 18972 KB Output is correct
13 Correct 1264 ms 18904 KB Output is correct
14 Correct 1099 ms 19016 KB Output is correct
15 Correct 1195 ms 18908 KB Output is correct
16 Correct 898 ms 18988 KB Output is correct
17 Correct 1169 ms 18812 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 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 58 ms 2988 KB Output is correct
7 Incorrect 155 ms 4392 KB Output isn't correct
8 Halted 0 ms 0 KB -