oj.uz

Submission #774662

# Submission time Handle Problem Language Result Execution time Memory
774662 2023-07-06T01:34:26 Z Magikarp4000 Radio Towers (IOI22_towers) C++17
14 / 100
 865 ms 5456 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 1e5+5;
int n,l,r,d;
int h[MAXN], le[MAXN], ri[MAXN], p[MAXN];
bool done;
bool z[MAXN];

void precalc() {
    PQ<PII> pq;
    FOR(i,0,n) {
        while (!pq.empty() && -pq.top().F <= h[i]-d) {
            ri[pq.top().S] = i;
            pq.pop();
        }
        pq.push({-h[i],i});
    }
    while (!pq.empty()) {
        ri[pq.top().S] = n;
        pq.pop();
    }
    FORR(i,n-1,-1) {
        while (!pq.empty() && -pq.top().F <= h[i]-d) {
            le[pq.top().S] = i;
            pq.pop();
        }
        pq.push({-h[i],i});
    }
    while (!pq.empty()) {
        le[pq.top().S] = -1;
        pq.pop();
    }
    vector<PII> v;
    FOR(i,0,n) v.PB({h[i],i});
    int vn = v.size();
    sort(ALL(v));
    set<int> s;
    s.insert(-INF);
    s.insert(INF);
    FOR(i,0,vn) {
        int idx = v[i].S;
        auto it = s.lower_bound(idx);
        auto it1 = it;
        it1--;
        if (le[idx] > (*it1) && ri[idx] < (*it)) s.insert(idx);
    }
    s.erase(-INF);
    s.erase(INF);
    FORX(u,s) {
        p[u+1]++;
        z[u] = 1;
    }
    FOR(i,1,n+1) p[i] += p[i-1];
    // FOR(i,0,n) cout << z[i] << " ";
    // cout << ln;
}

void init(int N, std::vector<int> H) {
    n = N;
    FOR(i,0,n) h[i] = H[i];
}

int max_towers(int L, int R, int D) {
    l = L, r = R, d = D;
    if (!done) {
        precalc();
        done = 1;
    }
    if (l == r) return 1;
    int res = p[r+1]-p[l];
    if (!z[l] && (l+1 >= n || h[l+1] > h[l])) res++;
    if (!z[r] && (r-1 < 0 || h[r-1] > h[r])) res++;
    // FOR(i,0,n) cout << le[i] << " ";
    // cout << ln;
    // FOR(i,0,n) cout << ri[i] << " ";
    // cout << ln;
    return res;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 412 ms 2396 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 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '91', found: '93'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '91', found: '93'
4 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 4564 KB Output is correct
2 Correct 753 ms 4636 KB Output is correct
3 Correct 690 ms 4696 KB Output is correct
4 Correct 590 ms 5420 KB Output is correct
5 Correct 759 ms 5440 KB Output is correct
6 Correct 769 ms 5416 KB Output is correct
7 Correct 820 ms 5376 KB Output is correct
8 Correct 493 ms 4116 KB Output is correct
9 Correct 619 ms 4120 KB Output is correct
10 Correct 865 ms 3872 KB Output is correct
11 Correct 827 ms 3992 KB Output is correct
12 Correct 502 ms 4120 KB Output is correct
13 Correct 585 ms 4116 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 296 KB Output is correct
17 Correct 42 ms 4584 KB Output is correct
18 Correct 44 ms 5380 KB Output is correct
19 Correct 44 ms 5456 KB Output is correct
20 Correct 31 ms 4164 KB Output is correct
21 Correct 27 ms 4120 KB Output is correct
22 Correct 42 ms 4628 KB Output is correct
23 Correct 48 ms 5416 KB Output is correct
24 Correct 50 ms 5416 KB Output is correct
25 Correct 22 ms 4128 KB Output is correct
26 Correct 22 ms 4028 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 1 ms 336 KB Output is correct

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '91', found: '93'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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