oj.uz

Submission #774773

# Submission time Handle Problem Language Result Execution time Memory
774773 2023-07-06T03:02:22 Z Magikarp4000 Radio Towers (IOI22_towers) C++17
14 / 100
 1043 ms 8564 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;

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, -1);
    }
    else {
        int tm = (tl+tr)/2;
        PII cur = {INF,-1};
        if (tp == 1) cur = {-INF,-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(-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);
    }
    FORX(u,s) {
        if (u == INF || u == -INF) 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(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];
    int a = *s.lower_bound(l);
    if (a == INF) 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 == -INF) 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 451 ms 3940 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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 408 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Incorrect 1 ms 336 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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 408 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Incorrect 1 ms 336 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 699 ms 7660 KB Output is correct
2 Correct 896 ms 7656 KB Output is correct
3 Correct 868 ms 7776 KB Output is correct
4 Correct 692 ms 8508 KB Output is correct
5 Correct 899 ms 8492 KB Output is correct
6 Correct 750 ms 8464 KB Output is correct
7 Correct 1043 ms 8464 KB Output is correct
8 Correct 717 ms 7236 KB Output is correct
9 Correct 788 ms 7212 KB Output is correct
10 Correct 702 ms 6976 KB Output is correct
11 Correct 809 ms 6972 KB Output is correct
12 Correct 878 ms 7228 KB Output is correct
13 Correct 858 ms 7192 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 336 KB Output is correct
17 Correct 56 ms 7700 KB Output is correct
18 Correct 58 ms 8484 KB Output is correct
19 Correct 58 ms 8468 KB Output is correct
20 Correct 41 ms 7192 KB Output is correct
21 Correct 37 ms 7256 KB Output is correct
22 Correct 56 ms 7684 KB Output is correct
23 Correct 57 ms 8564 KB Output is correct
24 Correct 58 ms 8484 KB Output is correct
25 Correct 41 ms 7208 KB Output is correct
26 Correct 36 ms 7140 KB Output is correct
27 Correct 1 ms 464 KB Output is correct
28 Correct 2 ms 464 KB Output is correct
29 Correct 1 ms 464 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 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 408 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 227 ms 2032 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 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 408 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Incorrect 1 ms 336 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 451 ms 3940 KB 11th lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -