oj.uz

Submission #626285

# Submission time Handle Problem Language Result Execution time Memory
626285 2022-08-11T10:55:42 Z kevinxiehk Radio Towers (IOI22_towers) C++17
4 / 100
 4000 ms 9508 KB 
#include "towers.h"

#include <bits/stdc++.h>

#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
#define int long long
using namespace std;

int n;
vector<int> h;
int pv[100005]; // 0: peak, 1: valley, 2: upslope, 3: downslope
int ps[100005];
int mx = 0;
int q = 0;
pair<int, int> seg[400005];
vector<pair<int, int>> ee;
int nn;

void build(int l, int r, int id) {
    if(l == r) seg[id] = mp(h[ee[l].fi], l);
    else {
        int m = (l + r) / 2;
        build(l, m, id * 2);
        build(m + 1, r, id * 2 + 1);
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }
    return;
}
void upd(int l, int r, int id, int k, int val) {
    if(l == r) seg[id] = mp(val, l);
    else {
        int m = (l + r) / 2;
        if(k <= m) upd(l, m, id * 2, k, val);
        else upd(m + 1, r, id * 2 + 1, k, val);
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }
    return;
}
pair<int, int> rmq (int l, int r, int id, int ql, int qr) {
    // cerr << l << ' ' << r << ' ' << id << ' ' << ql << ' ' << qr << '\n';
    if(ql > r || qr < l) return mp(-1, -1);
    if(ql <= l && qr >= r) return seg[id];
    int m = (l + r) / 2;
    return max(rmq(l, m, id * 2, ql, qr), rmq(m + 1, r, id * 2 + 1, ql, qr));
}
int lp[200005];

void init(signed N, vector<signed> H) {
    n = N;
    h.pb(2000000000);
    for(auto x: H) h.pb(x);
    h.pb(2000000000);
    ee.pb(mp(0, 0));
    for(int i = 1; i <= n; i++) {
        mx = max(mx, h[i]);
        if(h[i] < h[i - 1] && h[i] < h[i + 1]) pv[i] = 1;
        else if(h[i] > h[i - 1] && h[i] < h[i + 1]) pv[i] = 2;
        else if(h[i] < h[i - 1] && h[i] > h[i + 1]) pv[i] = 3;
        ps[i] = ps[i - 1];
        if(pv[i] == 1) ps[i]++;
        if(pv[i] <= 1) {
            ee.pb(mp(i, pv[i]));
        }
    }
    nn = ee.size() - 1;
    for(int i = 1; i <= 100000; i *= 2) {
        for(int j = i; j < i * 2; j++) lp[j] = i;
    }
    build(1, nn, 1);
    for(int i = 2; i <= nn; i++) {
        assert((pv[ee[i].fi] ^ pv[ee[i - 1].fi]) == 1);
    }
    // for(int i = 1; i <= n; i++) cerr << pv[i] << ' '; cerr << '\n';
    // cerr << nn << '\n';
    return;
}
int solve(int l, int r, int mx, int d) {
    assert(pv[ee[l].fi] == pv[ee[r].fi] && pv[ee[r].fi] == 1);
    // cerr << l << ' ' << r << ' ' << mx << ' ' << d  << '\n';
    if(mx <= 0) return 0;
    if(l > r) return 0;
    // if(l == r && pv[ee[l].se] == 1) return (h[ee[l].se] <= mx);
    assert(l >= 1 && r <= nn);
    auto aa = rmq(1, nn, 1, l, r);
    
    if(pv[ee[aa.se].fi] == 1) {
        assert(l == r);
        // cerr << l << ' ' << r << ' ' << mx << ' ' << d << ' ' << aa.fi << ' ' << aa.se << ' ' << (h[ee[l].fi] <= mx) << '\n';
        return (aa.fi <= mx);
    }
    int a = solve(l, aa.se - 1, min(mx, aa.fi - d), d) + solve(aa.se + 1, r, min(mx, aa.fi - d), d);
    int b = max(solve(l, aa.se - 1, mx, d), solve(aa.se + 1, r, mx, d));
    // cerr << l << ' ' << r << ' ' << mx << ' ' << d << ' ' << aa.fi << ' ' << aa.se << ' ' << max(a, b) << '\n';
    return max(a, b);
}

signed max_towers(signed l, signed r, signed d) {
    l++; r++; q++;
    if(r - l < 2) return 1;
    int el = 0;
    int er = 0;
    for(int i = lp[nn]; i > 0; i /= 2) {
        if(el + i <= nn && ee[el + i].fi < l) el += i;
        if(er + i <= nn && ee[er + i].fi <= r) er += i;
        // cerr << i << ' ' << nn << ' ' << el << ' ' << er << ' ' << ee[el].fi << ' ' << ee[er].fi << ' ' << l << ' ' << r << '\n';
    }
    el++;
    if(el > er) return 1;
    bool lc = false;
    bool rc = false;
    if(pv[l] == 2) {
        lc = true;
        el--;
        pv[l] = 1;
        upd(1, nn, 1, el, h[l]);
    }
    if(pv[r] == 3) {
        rc = true;
        er++;
        pv[r] = 1;
        upd(1, nn, 1, er, h[r]);
    }
    // cerr << el << ' ' << er << '\n';
    if(pv[ee[el].fi] == 0) el++;
    if(pv[ee[er].fi] == 0) er--;
    // cerr << el << ' ' << er << '\n';
    int kk;
    if(el >= er) kk = 1;
    else kk = solve(el, er, 1000000001, d);

    if(lc) {
        pv[l] = 2;
        upd(1, nn, 1, el, h[ee[el].fi]);
    }
    if(rc) {
        pv[r] = 3;
        upd(1, nn, 1, er, h[ee[er].fi]);
    }
    return max(1LL, kk);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 3368 KB Output is correct
2 Correct 729 ms 4548 KB Output is correct
3 Correct 721 ms 4520 KB Output is correct
4 Correct 861 ms 4524 KB Output is correct
5 Correct 882 ms 4524 KB Output is correct
6 Correct 981 ms 4480 KB Output is correct
7 Correct 857 ms 4540 KB Output is correct
8 Correct 1 ms 1232 KB Output is correct
9 Correct 1 ms 1360 KB Output is correct
10 Correct 1 ms 1360 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1360 KB Output is correct
2 Correct 266 ms 1512 KB Output is correct
3 Correct 171 ms 1504 KB Output is correct
4 Execution timed out 4098 ms 1488 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1360 KB Output is correct
2 Correct 266 ms 1512 KB Output is correct
3 Correct 171 ms 1504 KB Output is correct
4 Execution timed out 4098 ms 1488 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4035 ms 9508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4066 ms 2892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1360 KB Output is correct
2 Correct 266 ms 1512 KB Output is correct
3 Correct 171 ms 1504 KB Output is correct
4 Execution timed out 4098 ms 1488 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 3368 KB Output is correct
2 Correct 729 ms 4548 KB Output is correct
3 Correct 721 ms 4520 KB Output is correct
4 Correct 861 ms 4524 KB Output is correct
5 Correct 882 ms 4524 KB Output is correct
6 Correct 981 ms 4480 KB Output is correct
7 Correct 857 ms 4540 KB Output is correct
8 Correct 1 ms 1232 KB Output is correct
9 Correct 1 ms 1360 KB Output is correct
10 Correct 1 ms 1360 KB Output is correct
11 Correct 1 ms 1360 KB Output is correct
12 Correct 266 ms 1512 KB Output is correct
13 Correct 171 ms 1504 KB Output is correct
14 Execution timed out 4098 ms 1488 KB Time limit exceeded
15 Halted 0 ms 0 KB -