oj.uz

Submission #825133

# Submission time Handle Problem Language Result Execution time Memory
825133 2023-08-14T14:41:07 Z PixelCat Radio Towers (IOI22_towers) C++17
14 / 100
 662 ms 2256 KB 
#include "towers.h"

#ifdef NYAOWO
#include "stub.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second 
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

inline void chmax(int &x, int val) { x = max(x, val); }

const int MAXN = 100'000;

// #define L(id) ((id) * 2 + 1)
// #define R(id) ((id) * 2 + 2)
// struct SegTree {
//     int mx[MAXN * 4 + 10];
//     void build() {
//         memset(mx, 0, sizeof(mx));
//     }
//     void upd(int id, int l, int r, int pos, int val) {
//         if(l == r) {
//             chmax(mx[id], val);
//             return;
//         }
//         int m = (l + r) / 2;
//         if(pos <= m) upd(L(id), l, m, pos, val);
//         else         upd(R(id), m + 1, r, pos, val);
//         mx[id] = max(mx[L(id)], mx[R(id)]);
//     }
//     int range_max(int id, int l, int r, int L, int R) {
//         if(L > R) return 0;
//         if(l >= L && r <= R) {
//             return mx[id];
//         }
//         int m = (l + r) / 2;
//         int res = 0;
//         if(L <= m) chmax(res, range_max(L(id), l, m, L, R));
//         if(R > m)  chmax(res, range_max(R(id), m + 1, r, L, R));
//         return res;
//     }
// } dp1, dp2;

#define LO(x) ((x) & (-(x)))
struct BIT {
    int n;
    int a[MAXN + 10];
    void init(int _n) {
        n = _n;
        memset(a, 0, sizeof(a));
    }
    void add(int i, int x) {
        while(i <= n) {
            a[i] += x;
            i += LO(i);
        }
    }
    int sum(int i) {
        int res = 0;
        while(i) {
            res += a[i];
            i -= LO(i);
        }
        return res;
    }
} bit;

int n;
int h[MAXN + 10];
int vals[MAXN + 10];

void init(int N, std::vector<int> H) {
    n = N;
    For(i, 0, n - 1) {
        h[i] = H[i];
        vals[i] = h[i];
    }
    sort(vals, vals + n);

    bit.init(n);
    For(i, 1, n - 2) {
        if(h[i] < h[i - 1] && h[i] < h[i + 1]) {
            bit.add(i, 1);
        }
    }
}

int max_towers(int L, int R, int D) {
    if(L + 1 >= R) return 1;
    int ans = bit.sum(R - 1) - bit.sum(L);
    if(h[L] < h[L + 1]) ans++;
    if(h[R] < h[R - 1]) ans++;
    return ans;
    // int ans = 0;
    // dp1.build();
    // dp2.build();
    // For(i, L, R) {
    //     int p = (int)(lower_bound(vals, vals + n, h[i]) - vals);
    //     int l = (int)(upper_bound(vals, vals + n, h[i] - D) - vals) - 1;
    //     int r = (int)(lower_bound(vals, vals + n, h[i] + D) - vals);
    //     int v1 = dp2.range_max(0, 0, n - 1, r, n - 1) + 1;
    //     int v2 = dp1.range_max(0, 0, n - 1, 0, l);
    //     dp1.upd(0, 0, n - 1, p, v1);
    //     dp2.upd(0, 0, n - 1, p, v2);
    //     chmax(ans, v1);
    // }
    // return ans;
}

/*

7 3
10 20 60 40 50 30 70
1 5 10
2 2 100
0 6 17

3
1
2

*/

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 2212 KB Output is correct
2 Correct 611 ms 2228 KB Output is correct
3 Correct 612 ms 2256 KB Output is correct
4 Correct 433 ms 2212 KB Output is correct
5 Correct 627 ms 2224 KB Output is correct
6 Correct 522 ms 2220 KB Output is correct
7 Correct 662 ms 2236 KB Output is correct
8 Correct 656 ms 2236 KB Output is correct
9 Correct 589 ms 2216 KB Output is correct
10 Correct 594 ms 2236 KB Output is correct
11 Correct 475 ms 2220 KB Output is correct
12 Correct 642 ms 2116 KB Output is correct
13 Correct 616 ms 2220 KB Output is correct
14 Correct 0 ms 592 KB Output is correct
15 Correct 1 ms 720 KB Output is correct
16 Correct 1 ms 720 KB Output is correct
17 Correct 19 ms 2228 KB Output is correct
18 Correct 20 ms 2232 KB Output is correct
19 Correct 15 ms 2228 KB Output is correct
20 Correct 10 ms 2256 KB Output is correct
21 Correct 11 ms 2228 KB Output is correct
22 Correct 16 ms 2128 KB Output is correct
23 Correct 15 ms 2212 KB Output is correct
24 Correct 15 ms 2256 KB Output is correct
25 Correct 10 ms 2240 KB Output is correct
26 Correct 17 ms 2232 KB Output is correct
27 Correct 1 ms 720 KB Output is correct
28 Correct 1 ms 720 KB Output is correct
29 Correct 1 ms 720 KB Output is correct
30 Correct 1 ms 720 KB Output is correct
31 Correct 1 ms 720 KB Output is correct
32 Correct 1 ms 720 KB Output is correct
33 Correct 1 ms 720 KB Output is correct
34 Correct 1 ms 720 KB Output is correct
35 Correct 1 ms 720 KB Output is correct
36 Correct 1 ms 720 KB Output is correct

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

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