oj.uz

Submission #1056406

# Submission time Handle Problem Language Result Execution time Memory
1056406 2024-08-13T09:17:43 Z Forested Radio Towers (IOI22_towers) C++17
18 / 100
 553 ms 13628 KB 
#include <bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
template <typename T>
using VVV = V<V<V<T>>>;

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r)-1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define LEN(x) (i32) size(x)

void dbg(i32 x) { cerr << x; }
void dbg(i64 x) { cerr << x; }
template <typename T, typename U>
void dbg(pair<T, U> p) {
    cerr << '(' << p.first << ", " << p.second << ')';
}
template <typename T>
void dbg(V<T> arr) {
    cerr << '[';
    REP(i, LEN(arr)) {
        if (i) {
            cerr << ", ";
        }
        dbg(arr[i]);
    }
    cerr << ']';
}
void debug() { cerr << '\n'; }
template <typename Head, typename... Tail>
void debug(Head head, Tail... tail) {
    dbg(head);
    cerr << ", ";
    debug(tail...);
}
#ifdef DEBUGF
#define DBG(...)                       \
    do {                               \
        cerr << #__VA_ARGS__ << " : "; \
        debug(__VA_ARGS__);            \
    } while (false)
#else
#define DBG(...) (void)0
#endif

#include "towers.h"

constexpr i32 INF = 1001001001;

template <typename T>
i32 lob(const V<T> &arr, T v) {
    return (i32)(lower_bound(ALL(arr), v) - begin(arr));
}
template <typename T>
i32 upb(const V<T> &arr, T v) {
    return (i32)(upper_bound(ALL(arr), v) - begin(arr));
}


struct RMQ {
    i32 n;
    V<i32> dat;
    
    RMQ(i32 n) : n(n), dat(2 * n, -INF) {}
    
    void update(i32 idx, i32 val) {
        idx += n;
        dat[idx] = val;
        while ((idx /= 2) >= 1) {
            dat[idx] = max(dat[2 * idx], dat[2 * idx + 1]);
        }
    }
    
    i32 rmq(i32 l, i32 r) const {
        l += n;
        r += n;
        i32 m = -INF;
        while (l < r) {
            if (l & 1) {
                chmax(m, dat[l++]);
            }
            if (r & 1) {
                chmax(m, dat[--r]);
            }
            l /= 2;
            r /= 2;
        }
        return m;
    }
    
    void trc() const {
        V<i32> arr(n + ALL(dat));
        DBG(arr);
    }
};

template <typename T>
class RemovableQueue {
    priority_queue<T, V<T>, greater<>> pq, rm;
    
public:
    RemovableQueue() : pq(), rm() {}
    void add(T x) {
        pq.push(x);
    }
    void remove(T x) {
        rm.push(x);
    }
    T getmin() {
        while (!rm.empty() && rm.top() == pq.top()) {
            rm.pop();
            pq.top();
        }
        return pq.top();
    }
    i32 size() const {
        return (i32)pq.size() - (i32)rm.size();
    }
};

V<pair<i32, i32>> calc_all_ans(i32 n, V<i32> h) {
    V<pair<i32, i32>> ret;
    V<i32> down(n, 0), up(n, 0);
    REP(i, 1, n - 1) {
        if (h[i - 1] < h[i] && h[i] > h[i + 1]) {
            up[i] = 1;
        }
        if (h[i - 1] > h[i] && h[i] < h[i + 1]) {
            down[i] = 1;
        }
    }
    if (accumulate(ALL(up), 0) == 0) {
        ret.emplace_back(1, 1);
        return ret;
    }
    i32 l = 0;
    while (h[l] > h[l + 1]) {
        ++l;
    }
    i32 r = n;
    while (h[r - 2] < h[r - 1]) {
        --r;
    }
    down[l] = down[r - 1] = 1;
    V<i32> imp;
    REP(i, n) {
        if (down[i] || up[i]) {
            imp.push_back(i);
        }
    }
    DBG(imp);
    RemovableQueue<tuple<i32, i32, i32>> pq;
    V<i32> lft(LEN(imp), -1), rgt(LEN(imp), -1);
    REP(i, LEN(imp) - 1) {
        pq.add(make_tuple(abs(h[imp[i]] - h[imp[i + 1]]), i, i + 1));
        lft[i + 1] = i;
        rgt[i] = i + 1;
    }
    ret.emplace_back(1, LEN(pq) / 2 + 1);
    while (LEN(pq) >= 2) {
        auto [d, l, r] = pq.getmin();
        ret.emplace_back(d + 1, LEN(pq) / 2);
        pq.remove(make_tuple(d, l, r));
        i32 ll = lft[l], rr = rgt[r];
        if (ll != -1) {
            pq.remove(make_tuple(abs(h[imp[ll]] - h[imp[l]]), ll, l));
            rgt[ll] = rr;
        }
        if (rr != -1) {
            pq.remove(make_tuple(abs(h[imp[r]] - h[imp[rr]]), r, rr));
            lft[rr] = ll;
        }
        if (ll != -1 && rr != -1) {
            pq.add(make_tuple(abs(h[imp[ll]] - h[imp[rr]]), ll, rr));
        }
    }
    V<pair<i32, i32>> simp;
    REP(i, LEN(ret)) {
        if (i == LEN(ret) - 1 || ret[i].first != ret[i + 1].first) {
            simp.push_back(ret[i]);
        }
    }
    ret = simp;
    DBG(ret);
    return ret;
}

i32 n;
V<i32> h;
V<i32> psum;
i32 peak;
V<pair<i32, i32>> allans;

void init(i32 _n, V<i32> _h) {
    n = _n;
    h = _h;
    
    psum.resize(n + 1, 0);
    REP(i, n) {
        psum[i + 1] = psum[i] + (0 < i && i < n - 1 && h[i - 1] < h[i] && h[i] > h[i + 1]);
    }
    
    {
        i32 mi = (i32)(max_element(ALL(h)) - begin(h));
        peak = mi;
        REP(i, mi) {
            if (h[i] > h[i + 1]) {
                peak = -1;
            }
        }
        REP(i, mi, n - 1) {
            if (h[i] < h[i + 1]) {
                peak = -1;
            }
        }
    }
    
    allans = calc_all_ans(n, h);
}

i32 max_towers(i32 l, i32 r, i32 delta) {
    ++r;
    if (r - l == 1) {
        return 1;
    }
    
    if (delta == 1) {
        i32 ans = psum[r - 1] - psum[l + 1] + 1;
        return ans;
    }
    
    if (peak != -1) {
        if (l <= peak && peak < r && max(h[l], h[r - 1]) + delta <= h[peak]) {
            return 2;
        } else {
            return 1;
        }
    }
    
    if (l == 0 && r == n) {
        auto itr = lower_bound(ALL(allans), pair<i32, i32>(delta + 1, 0));
        --itr;
        return itr->second;
    }
    
    V<i32> g(begin(h) + l, begin(h) + r);
    i32 m = r - l;
    
    V<i32> hs;
    hs.reserve(3 * m);
    REP(i, m) {
        hs.push_back(g[i] - delta);
        hs.push_back(g[i]);
        hs.push_back(g[i] + delta);
    }
    sort(ALL(hs));
    hs.erase(unique(ALL(hs)), end(hs));
    i32 k = LEN(hs);
    RMQ down(k);
    RMQ up(k);
    
    REP(i, m) {
        i32 d = max(1, up.rmq(lob(hs, g[i] + delta), k) + 1);
        i32 u = down.rmq(0, lob(hs, g[i] - delta) + 1);
        i32 idx = lob(hs, g[i]);
        down.update(idx, d);
        up.update(idx, u);
    }
    i32 ans = down.rmq(0, k);
    return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 1880 KB Output is correct
2 Correct 512 ms 3160 KB Output is correct
3 Correct 501 ms 3136 KB Output is correct
4 Correct 514 ms 3160 KB Output is correct
5 Correct 523 ms 3160 KB Output is correct
6 Correct 532 ms 3160 KB Output is correct
7 Correct 538 ms 3160 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 0 ms 512 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '34', found: '1'
26 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '34', found: '1'
26 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 11304 KB Output is correct
2 Correct 483 ms 11592 KB Output is correct
3 Correct 516 ms 11336 KB Output is correct
4 Correct 480 ms 12880 KB Output is correct
5 Correct 492 ms 12904 KB Output is correct
6 Correct 553 ms 12828 KB Output is correct
7 Correct 488 ms 13124 KB Output is correct
8 Correct 545 ms 3160 KB Output is correct
9 Correct 489 ms 3160 KB Output is correct
10 Correct 532 ms 3160 KB Output is correct
11 Correct 455 ms 3160 KB Output is correct
12 Correct 413 ms 3144 KB Output is correct
13 Correct 384 ms 3132 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 27 ms 11056 KB Output is correct
18 Correct 25 ms 12996 KB Output is correct
19 Correct 26 ms 12912 KB Output is correct
20 Correct 8 ms 3160 KB Output is correct
21 Correct 14 ms 3160 KB Output is correct
22 Correct 23 ms 11076 KB Output is correct
23 Correct 38 ms 13628 KB Output is correct
24 Correct 30 ms 12860 KB Output is correct
25 Correct 8 ms 3160 KB Output is correct
26 Correct 14 ms 3160 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 1 ms 600 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 556 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 1 ms 600 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 0 ms 344 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 151 ms 2436 KB 1st lines differ - on the 1st token, expected: '7197', found: '1'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '34', found: '1'
26 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 1880 KB Output is correct
2 Correct 512 ms 3160 KB Output is correct
3 Correct 501 ms 3136 KB Output is correct
4 Correct 514 ms 3160 KB Output is correct
5 Correct 523 ms 3160 KB Output is correct
6 Correct 532 ms 3160 KB Output is correct
7 Correct 538 ms 3160 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 0 ms 512 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 600 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '34', found: '1'
36 Halted 0 ms 0 KB -