oj.uz

Submission #1079478

# Submission time Handle Problem Language Result Execution time Memory
1079478 2024-08-28T15:35:59 Z ProtonDecay314 Radio Towers (IOI22_towers) C++17
28 / 100
 1432 ms 85468 KB 
// AM + DG
#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

/*
DTree (DiffTree)

Computes the largest forward difference within a range

Formally, max l <= i <= j <= r of h[j] - h[i]
*/
struct DTreeState {
    int mn, mx, difff, diffb;

    DTreeState operator+(const DTreeState& o) const {
        if(mn == 0) return o;
        else if(o.mn == 0) return {mn, mx, difff, diffb};
        return {min(mn, o.mn), max(mx, o.mx), max(difff, o.mx - mn), max(diffb, mx - o.mn)};
    }
};

class DTree {
    public:
        int l, r;
        DTree *lt, *rt;
        DTreeState v;

        DTree(int a_l, int a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), v({0, 0, 0}) {}

        void combine() {
            v = lt->v + rt->v; // ! Careful! Addition is noncommutative!
        }

        void build(const vi& a) {
            if(l == r) {
                v = {a[l], a[l], 0, 0};

                return;
            }

            int m = (l + r) >> 1;

            lt = new DTree(l, m);

            rt = new DTree(m + 1, r);

            lt->build(a);
            rt->build(a);

            combine();
        }

        DTreeState qry(int ql, int qr) {
            if(ql > r || qr < l) return {0, 0, 0, 0};

            if(ql == l && qr == r) {
                return v;
            }

            int m = (l + r) >> 1;

            return lt->qry(ql, min(qr, m)) + rt->qry(max(ql, m + 1) , qr);
        }
};

/*
LTree (Lease Tree)

The lease tree will compute the maximum and minimum indices to be leased
if the value of delta is D

Notice that each node has a corresponding max delta and index

Now, what if we store the deltas in increasing order? (could be decreasing too)

Then, when the value of delta is D, that means that a suffix (or prefix) would
be the values in consideration

Well, now, what if we compute the min and max indices over a prefix?

So it reduces to binary search ^^

It reduces to two binary searches, actually, so Q log^2 N per query

Conceptually, a node would have a schema of...

type Node = {
    l, r: int
    lt, rt: Node*
    deltas: [delta, ind][]
    mins: int[]
    maxs: int[]
}
*/
class LTree {
    public:
        int l, r;
        LTree *lt, *rt;
        vpi deltas;
        vi mins;
        vi maxs;

        LTree(int a_l, int a_r): l(a_l), r(a_r), deltas(), mins(), maxs() {}
        
        void combine() {
            int lds = lt->deltas.size(), rds = rt->deltas.size();

            int ldp = 0, rdp = 0;

            while(ldp < lds && rdp < rds) {
                if(lt->deltas[ldp].fi > rt->deltas[rdp].fi) {
                    deltas.pb(lt->deltas[ldp]);
                    ldp++;
                } else {
                    deltas.pb(rt->deltas[rdp]);
                    rdp++;
                }
            }

            while(ldp < lds) {
                deltas.pb(lt->deltas[ldp]);
                ldp++;
            }

            while(rdp < rds) {
                deltas.pb(rt->deltas[rdp]);
                rdp++;
            }

            int ds = deltas.size();

            mins.reserve(ds);
            maxs.reserve(ds);

            mins.pb(INF(int));
            maxs.pb(NINF(int));

            for(int i = 0; i < ds; i++) {
                mins.pb(min(mins.back(), deltas[i].se));
                maxs.pb(max(maxs.back(), deltas[i].se));
            }
        }

        void build(const vi& d) {
            if(l == r) {
                deltas.pb({d[l], l});
                mins.pb(INF(int));
                mins.pb(l);
                maxs.pb(NINF(int));
                maxs.pb(l);
                return;
            }

            int m = (l + r) >> 1;

            lt = new LTree(l, m);
            rt = new LTree(m + 1, r);

            lt->build(d);
            rt->build(d);

            combine();
        }

        pi qry(int ql, int qr, int d) {
            if(ql > r || qr < l) return {INF(int), NINF(int)};

            if(ql == l && qr == r) {
                int ds = deltas.size();
                int li = -1, ri = ds;

                while(ri - li > 1) {
                    int m = (li + ri) >> 1;

                    if(deltas[m].fi >= d) li = m;
                    else ri = m;
                }

                return {mins[li + 1], maxs[li + 1]};
            }

            int m = (l + r) >> 1;

            auto [mn1, mx1] = lt->qry(ql, min(qr, m), d);
            auto [mn2, mx2] = rt->qry(max(m + 1, ql), qr, d);

            return {min(mn1, mn2), max(mx1, mx2)};
        }

        int qry_count(int ql, int qr, int d) {
            if(ql > r || qr < l) return 0;

            if(ql == l && qr == r) {
                int ds = deltas.size();
                int li = -1, ri = ds;

                while(ri - li > 1) {
                    int m = (li + ri) >> 1;

                    if(deltas[m].fi >= d) li = m;
                    else ri = m;
                }

                return li + 1;
            }

            int m = (l + r) >> 1;

            return lt->qry_count(ql, min(qr, m), d) + rt->qry_count(max(m + 1, ql), qr, d);
        }
};

int n;
vi h;

DTree* dtr;
LTree* ltr;
vi dvals;

void init(int N, vi H) {
    n = N;
    h = H;

    // Create DTree
    dtr = new DTree(0, n - 1);

    dtr->build(h);

    // Compute critical d-values
    for(int i = 0; i < n; i++) {
        int l1 = -1, r1 = i;

        while(r1 - l1 > 1) {
            int m = (l1 + r1) >> 1;

            if(dtr->qry(m, i).mn < h[i]) l1 = m;
            else r1 = m;
        }

        int l2 = i, r2 = n;

        while(r2 - l2 > 1) {
            int m = (l2 + r2) >> 1;

            if(dtr->qry(i, m).mn < h[i]) r2 = m;
            else l2 = m;
        }
        
        int min_h = INF(int);

        if(l1 != -1) {
            min_h = min(min_h, dtr->qry(l1, i).mx);
        }

        if(r2 != n) {
            min_h = min(min_h, dtr->qry(i, r2).mx);
        }

        dvals.pb(min_h - h[i]);
    }

    ltr = new LTree(0, n - 1);
    ltr->build(dvals);
}

int max_towers(int L, int R, int D) {
    auto [li, ri] = ltr->qry(L, R, D);
    // cout << "! " << li << " " << ri << endl;
    int ans = 0;

    if(li == INF(int)) {
        // Case 1 (wow, research follows me everywhere): no leased in the range
        // Check forward and backward largest diffs

        auto state = dtr->qry(L, R);

        if(state.diffb >= D) ans++;
        if(state.difff >= D) ans++;
    } else {
        // Case 2 (res reference???): there is at least one leased in the range
        ans = ltr->qry_count(L, R, D);

        if(dtr->qry(L, li - 1).difff >= D) ans++;
        if(dtr->qry(ri + 1, R).diffb >= D) ans++;
    }

    return max(ans, 1);
}

/*
Last frontier
kodoku na hoshitachi e sasageru uta wo
Last moment
hitori de saihate e tabidatsu uta wo
Last of all
majiwaru koto no nai sekai wo
ima kaeru kara saigo ni
kimi to boku wa deau
*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 805 ms 49352 KB 45th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 8 ms 1672 KB Output is correct
3 Correct 6 ms 1880 KB Output is correct
4 Correct 6 ms 1880 KB Output is correct
5 Correct 6 ms 1728 KB Output is correct
6 Correct 7 ms 1880 KB Output is correct
7 Correct 6 ms 1880 KB Output is correct
8 Correct 6 ms 1676 KB Output is correct
9 Correct 5 ms 1880 KB Output is correct
10 Correct 6 ms 1664 KB Output is correct
11 Correct 6 ms 1660 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 6 ms 1880 KB Output is correct
14 Correct 6 ms 1880 KB Output is correct
15 Correct 6 ms 1880 KB Output is correct
16 Correct 6 ms 1664 KB Output is correct
17 Correct 6 ms 1880 KB Output is correct
18 Correct 6 ms 1880 KB Output is correct
19 Correct 6 ms 1880 KB Output is correct
20 Correct 10 ms 1680 KB Output is correct
21 Correct 6 ms 1880 KB Output is correct
22 Correct 6 ms 1880 KB Output is correct
23 Correct 5 ms 1880 KB Output is correct
24 Correct 5 ms 1688 KB Output is correct
25 Correct 2 ms 856 KB Output is correct
26 Correct 6 ms 1880 KB Output is correct
27 Correct 6 ms 1676 KB Output is correct
28 Correct 6 ms 1880 KB Output is correct
29 Correct 6 ms 1880 KB Output is correct
30 Correct 10 ms 1880 KB Output is correct
31 Correct 7 ms 1880 KB Output is correct
32 Correct 5 ms 1880 KB Output is correct
33 Correct 6 ms 1880 KB Output is correct
34 Correct 7 ms 1880 KB Output is correct
35 Correct 6 ms 1880 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 8 ms 1672 KB Output is correct
3 Correct 6 ms 1880 KB Output is correct
4 Correct 6 ms 1880 KB Output is correct
5 Correct 6 ms 1728 KB Output is correct
6 Correct 7 ms 1880 KB Output is correct
7 Correct 6 ms 1880 KB Output is correct
8 Correct 6 ms 1676 KB Output is correct
9 Correct 5 ms 1880 KB Output is correct
10 Correct 6 ms 1664 KB Output is correct
11 Correct 6 ms 1660 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 6 ms 1880 KB Output is correct
14 Correct 6 ms 1880 KB Output is correct
15 Correct 6 ms 1880 KB Output is correct
16 Correct 6 ms 1664 KB Output is correct
17 Correct 6 ms 1880 KB Output is correct
18 Correct 6 ms 1880 KB Output is correct
19 Correct 6 ms 1880 KB Output is correct
20 Correct 10 ms 1680 KB Output is correct
21 Correct 6 ms 1880 KB Output is correct
22 Correct 6 ms 1880 KB Output is correct
23 Correct 5 ms 1880 KB Output is correct
24 Correct 5 ms 1688 KB Output is correct
25 Correct 2 ms 856 KB Output is correct
26 Correct 6 ms 1880 KB Output is correct
27 Correct 6 ms 1676 KB Output is correct
28 Correct 6 ms 1880 KB Output is correct
29 Correct 6 ms 1880 KB Output is correct
30 Correct 10 ms 1880 KB Output is correct
31 Correct 7 ms 1880 KB Output is correct
32 Correct 5 ms 1880 KB Output is correct
33 Correct 6 ms 1880 KB Output is correct
34 Correct 7 ms 1880 KB Output is correct
35 Correct 6 ms 1880 KB Output is correct
36 Correct 336 ms 53488 KB Output is correct
37 Incorrect 563 ms 85404 KB 1st lines differ - on the 1st token, expected: '2946', found: '2945'
38 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1432 ms 84704 KB 29th lines differ - on the 1st token, expected: '9839', found: '9838'
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 20064 KB Output is correct
2 Correct 1292 ms 85384 KB Output is correct
3 Correct 1304 ms 85400 KB Output is correct
4 Correct 1265 ms 85188 KB Output is correct
5 Correct 1259 ms 85188 KB Output is correct
6 Correct 1297 ms 85396 KB Output is correct
7 Correct 1242 ms 85296 KB Output is correct
8 Correct 1271 ms 85188 KB Output is correct
9 Correct 1222 ms 85412 KB Output is correct
10 Correct 1236 ms 85188 KB Output is correct
11 Correct 1268 ms 85188 KB Output is correct
12 Correct 554 ms 85416 KB Output is correct
13 Correct 561 ms 85188 KB Output is correct
14 Correct 567 ms 85312 KB Output is correct
15 Correct 550 ms 85188 KB Output is correct
16 Correct 607 ms 85188 KB Output is correct
17 Correct 551 ms 82504 KB Output is correct
18 Correct 574 ms 85188 KB Output is correct
19 Correct 570 ms 85468 KB Output is correct
20 Correct 566 ms 85316 KB Output is correct
21 Correct 592 ms 85188 KB Output is correct
22 Correct 562 ms 85188 KB Output is correct
23 Correct 570 ms 85188 KB Output is correct
24 Correct 544 ms 85188 KB Output is correct
25 Correct 603 ms 85188 KB Output is correct
26 Correct 583 ms 85240 KB Output is correct
27 Correct 547 ms 85188 KB Output is correct
28 Correct 6 ms 1680 KB Output is correct
29 Correct 6 ms 1880 KB Output is correct
30 Correct 6 ms 1880 KB Output is correct
31 Correct 6 ms 1880 KB Output is correct
32 Correct 6 ms 1660 KB Output is correct
33 Correct 3 ms 856 KB Output is correct
34 Correct 6 ms 1676 KB Output is correct
35 Correct 6 ms 1880 KB Output is correct
36 Correct 6 ms 1880 KB Output is correct
37 Correct 8 ms 1880 KB Output is correct
38 Correct 6 ms 1880 KB Output is correct
39 Correct 7 ms 1880 KB Output is correct
40 Correct 6 ms 1880 KB Output is correct
41 Correct 5 ms 1880 KB Output is correct
42 Correct 5 ms 1880 KB Output is correct
43 Correct 6 ms 1880 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 8 ms 1672 KB Output is correct
3 Correct 6 ms 1880 KB Output is correct
4 Correct 6 ms 1880 KB Output is correct
5 Correct 6 ms 1728 KB Output is correct
6 Correct 7 ms 1880 KB Output is correct
7 Correct 6 ms 1880 KB Output is correct
8 Correct 6 ms 1676 KB Output is correct
9 Correct 5 ms 1880 KB Output is correct
10 Correct 6 ms 1664 KB Output is correct
11 Correct 6 ms 1660 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 6 ms 1880 KB Output is correct
14 Correct 6 ms 1880 KB Output is correct
15 Correct 6 ms 1880 KB Output is correct
16 Correct 6 ms 1664 KB Output is correct
17 Correct 6 ms 1880 KB Output is correct
18 Correct 6 ms 1880 KB Output is correct
19 Correct 6 ms 1880 KB Output is correct
20 Correct 10 ms 1680 KB Output is correct
21 Correct 6 ms 1880 KB Output is correct
22 Correct 6 ms 1880 KB Output is correct
23 Correct 5 ms 1880 KB Output is correct
24 Correct 5 ms 1688 KB Output is correct
25 Correct 2 ms 856 KB Output is correct
26 Correct 6 ms 1880 KB Output is correct
27 Correct 6 ms 1676 KB Output is correct
28 Correct 6 ms 1880 KB Output is correct
29 Correct 6 ms 1880 KB Output is correct
30 Correct 10 ms 1880 KB Output is correct
31 Correct 7 ms 1880 KB Output is correct
32 Correct 5 ms 1880 KB Output is correct
33 Correct 6 ms 1880 KB Output is correct
34 Correct 7 ms 1880 KB Output is correct
35 Correct 6 ms 1880 KB Output is correct
36 Correct 336 ms 53488 KB Output is correct
37 Incorrect 563 ms 85404 KB 1st lines differ - on the 1st token, expected: '2946', found: '2945'
38 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 805 ms 49352 KB 45th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -