oj.uz

Submission #434718

# Submission time Handle Problem Language Result Execution time Memory
434718 2021-06-21T15:29:09 Z yuto1115 Comparing Plants (IOI20_plants) C++17
44 / 100
 855 ms 11876 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;

void init(int _k, vi r) {
    k = _k;
    n = r.size();
//    if (k == 2) {
//
//    } else if (n <= 300) {
//
//    } else {
        p.assign(n, -1);
        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);
        };
        rep(i, n) if (!r[i]) check(i);
        rrep(t, n) {
//            assert(can.size() == 1);
            int nx = *can.begin();
            can.erase(nx);
            p[nx] = t;
            erase(nx);
        }
//    }
}

int compare_plants(int x, int y) {
//    if (k == 2) {
//
//    } else if (n <= 300) {
//
//    } else if (x == 0) {
//
//    } 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 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 3 ms 204 KB Output is correct
5 Correct 1 ms 248 KB Output is correct
6 Correct 6 ms 380 KB Output is correct
7 Correct 130 ms 3320 KB Output is correct
8 Correct 3 ms 280 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 103 ms 3244 KB Output is correct
11 Correct 70 ms 3260 KB Output is correct
12 Correct 69 ms 3384 KB Output is correct
13 Correct 77 ms 3240 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 3 ms 204 KB Output is correct
5 Correct 1 ms 248 KB Output is correct
6 Correct 6 ms 380 KB Output is correct
7 Correct 130 ms 3320 KB Output is correct
8 Correct 3 ms 280 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 103 ms 3244 KB Output is correct
11 Correct 70 ms 3260 KB Output is correct
12 Correct 69 ms 3384 KB Output is correct
13 Correct 77 ms 3240 KB Output is correct
14 Correct 145 ms 3812 KB Output is correct
15 Correct 786 ms 11788 KB Output is correct
16 Correct 130 ms 3632 KB Output is correct
17 Correct 855 ms 11792 KB Output is correct
18 Correct 574 ms 11796 KB Output is correct
19 Correct 540 ms 11792 KB Output is correct
20 Correct 796 ms 11852 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 0 ms 204 KB Output is correct
3 Correct 67 ms 3148 KB Output is correct
4 Correct 445 ms 11788 KB Output is correct
5 Correct 492 ms 11788 KB Output is correct
6 Correct 573 ms 11792 KB Output is correct
7 Correct 761 ms 11784 KB Output is correct
8 Correct 731 ms 11792 KB Output is correct
9 Correct 537 ms 11732 KB Output is correct
10 Correct 486 ms 11876 KB Output is correct
11 Correct 410 ms 11708 KB Output is correct
12 Correct 451 ms 11716 KB Output is correct
13 Correct 530 ms 11744 KB Output is correct

Subtask #5
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 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 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 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -