oj.uz

Submission #774779

# Submission time Handle Problem Language Result Execution time Memory
774779 2023-07-06T03:12:10 Z Magikarp4000 Radio Towers (IOI22_towers) C++17
14 / 100
 932 ms 13988 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;
#define int long long

struct Node {
    int ma,mi,pos;
};

const int MAXN = 1e5+5;
int n,l,r,d;
int h[MAXN], le[MAXN], ri[MAXN], p[MAXN];
bool done, z[MAXN];
Node st[MAXN*4+10];
set<int> s;

void update(int s, int tl, int tr, int idx, int val) {
    if (tl == tr) {
        st[s].ma = st[s].mi = val;
        st[s].pos = tl;
    }
    else {
        int tm = (tl+tr)/2;
        if (idx <= tm) update(s*2,tl,tm,idx,val);
        else update(s*2+1,tm+1,tr,idx,val);
        st[s].ma = max(st[s*2].ma, st[s*2+1].ma);
        st[s].pos = st[s*2].ma > st[s*2+1].ma ? st[s*2].pos : st[s*2+1].pos;
        st[s].mi = min(st[s*2].mi, st[s*2+1].mi);
    }
}

PII query(int s, int tl, int tr, int l, int r, int tp) {
    // tp is type of query
    // 0: range min
    // 1: index of range max
    if (l <= tl && r >= tr) {
        return tp == 1 ? make_pair(st[s].ma, st[s].pos) : make_pair(st[s].mi, -1LL);
    }
    else {
        int tm = (tl+tr)/2;
        PII cur = {LLINF,-1};
        if (tp == 1) cur = {-LLINF,-1};
        if (l <= tm) cur = query(s*2,tl,tm,l,r,tp);
        if (r > tm) {
            PII ncur = query(s*2+1,tm+1,tr,l,r,tp);
            if (tp == 0) {
                if (ncur.F < cur.F) cur = ncur;
            }
            else {
                if (ncur.F > cur.F) cur = ncur;
            }
        }
        return cur;
    }
}

void precalc() {
    FOR(i,0,n) update(1,0,n-1,i,h[i]);
    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));
    s.insert(-LLINF);
    s.insert(LLINF);
    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);
    }
    FORX(u,s) {
        if (u == LLINF || u == -LLINF) continue;
        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(int32_t N, std::vector<int32_t> H) {
    n = N;
    FOR(i,0,n) h[i] = H[i]*1LL;
}

int32_t max_towers(int32_t L, int32_t R, int32_t D) {
    l = L, r = R, d = D;
    if (!done) {
        precalc();
        done = 1;
    }
    if (l == r) return 1;
    int res = p[r+1]-p[l];
    int a = *s.lower_bound(l);
    if (a == LLINF) a = n;
    if (a > l+1) {
        int idx = query(1,0,n-1,l,a-1,1).S;
        if (idx > l) {
            int x = query(1,0,n-1,l,idx-1,0).F;
            if (x <= h[idx]-d) res++;
        }
    }
    auto it = s.upper_bound(r);
    it--;
    int b = *it;
    if (b == -LLINF) b = -1;
    if (b < r-1) {
        int idx = query(1,0,n-1,b+1,r,1).S;
        if (idx < r) {
            int x = query(1,0,n-1,idx+1,r,0).F;
            if (x <= h[idx]-d) res++;
        }
    }
    return res;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 358 ms 7384 KB 11th lines differ - on the 1st token, expected: '1', found: '0'
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 464 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Incorrect 1 ms 464 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
11 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 464 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Incorrect 1 ms 464 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
11 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 13068 KB Output is correct
2 Correct 932 ms 13148 KB Output is correct
3 Correct 871 ms 13188 KB Output is correct
4 Correct 895 ms 13880 KB Output is correct
5 Correct 785 ms 13968 KB Output is correct
6 Correct 832 ms 13964 KB Output is correct
7 Correct 782 ms 13988 KB Output is correct
8 Correct 835 ms 13736 KB Output is correct
9 Correct 865 ms 13760 KB Output is correct
10 Correct 834 ms 13396 KB Output is correct
11 Correct 747 ms 13440 KB Output is correct
12 Correct 740 ms 13752 KB Output is correct
13 Correct 835 ms 13748 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 464 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 58 ms 13088 KB Output is correct
18 Correct 59 ms 13948 KB Output is correct
19 Correct 60 ms 13880 KB Output is correct
20 Correct 44 ms 13764 KB Output is correct
21 Correct 39 ms 13752 KB Output is correct
22 Correct 65 ms 13088 KB Output is correct
23 Correct 60 ms 13968 KB Output is correct
24 Correct 61 ms 13988 KB Output is correct
25 Correct 39 ms 13840 KB Output is correct
26 Correct 46 ms 13624 KB Output is correct
27 Correct 1 ms 464 KB Output is correct
28 Correct 1 ms 464 KB Output is correct
29 Correct 1 ms 464 KB Output is correct
30 Correct 1 ms 592 KB Output is correct
31 Correct 1 ms 464 KB Output is correct
32 Correct 1 ms 464 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 464 KB Output is correct
35 Correct 1 ms 592 KB Output is correct
36 Correct 1 ms 464 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 3468 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 464 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Incorrect 1 ms 464 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
11 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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