oj.uz

Submission #914789

# Submission time Handle Problem Language Result Execution time Memory
914789 2024-01-22T16:59:44 Z vjudge1 Radio Towers (IOI22_towers) C++17
21 / 100
 771 ms 55888 KB 
#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define F(i, l, r) for (ll i = ll(l); i < ll(r); ++i)
#define FD(i, l, r) for (ll i = ll(l); i > ll(r); --i)
#define A(a) (a).begin(), (a).end()
#define K first
#define V second

template<typename T> struct SparseTable {
    int n,log2=0;
    function<T(T, T)> merge;
    T id ;
    vector<vector<T>> a = {{}};
    SparseTable(const vector<T>& v, function<T(T, T)> _merge, T _id): merge(_merge), id(_id) {
        n = v.size();
        while((1<<log2) <= n) {
            ++log2;
        }
        a.resize(log2);
        a[0] = v;
        for(int i=1,len=1;i<log2;++i,len*=2) {
            a[i].resize(n + 1 - (1<<i));
            for(size_t j=0;j<a[i].size();++j) {
                a[i][j] = merge(a[i-1][j], a[i-1][j + len]);
            }
        }
    }
    SparseTable(){}
    T query(int l, int r) { // [l,r)
        if (r <= l) return id;
        int len = __lg(r-l);
        return merge(a[len][l], a[len][r- (1<<len)]);
    }   
};

SparseTable<ll> spmin;
 

const int MAXN = 100010, INF = 1000000010;

namespace seg {
    pl merge(pl a, pl b) {
        return pair(min(a.K, b.K), max(a.V, b.V));
    }

    struct node{
        vector<pl> vec;
        vector<pl> indices; // {mn, mx}
        node(){};
        node(int value, int pos){
            vec.emplace_back(value, pos);
            indices.emplace_back(pos, pos);
        }
        node(node& a, node& b){
            vec.resize(a.vec.size() + b.vec.size());
            indices.resize(vec.size());
            merge(a.vec.begin(), a.vec.end(), b.vec.begin(), b.vec.end(), vec.begin());
            pl cur(MAXN, -1);

            // All items are now in sorted order, relative to first key.
            // Now mn and max represent the range of indices or something?  
            // for the suffix max.
            FD(i, ll(vec.size())-1, -1) indices[i] = merge(pair(vec[i].V, vec[i].V), cur);
        }
    };

    node tr[2*MAXN];

    pair<int, pl> query(int l, int r, int x){
        int ret=0;
        pl res(MAXN, -1);

        auto handle = [&](node& cur) {
            auto &[vec, indices] = cur;
            auto itr = lower_bound(A(vec), pair(x, -1));
            int pos = (int)(itr - vec.begin());
            ret += (int)(vec.end() - itr);
            if(itr!=vec.end()) res = merge(res, indices[pos]);
        };

        for(l+=MAXN, r+=MAXN; l<r; l>>=1, r>>=1){
            if(l&1) handle(tr[l++]);
            if(r&1) handle(tr[--r]);
        }

        return {ret, res};
    }

    void build(vl res) {
        F(i, 0, res.size()) seg::tr[MAXN+i]=seg::node(res[i], i);
        FD(i, MAXN-1, -1) tr[i]=node(tr[i<<1], tr[i<<1|1]);
    }
}
 
 
int arr[MAXN];
 
void init(int n, vector<int> H) {
    vl maxl(n), maxr(n);
    copy(A(H), arr);

    spmin = SparseTable<ll>(H, [](ll a, ll b) {
        return min(a, b);
    }, INF);

    F(i, 0, n) {
        int x;
        for(x=i-1; x!=-1 && H[x]<H[i]; x=maxl[x]);
        maxl[i]=x;
    }

    FD(i, n-1, -1) {
        int x;
        for(x=i+1; x!=n && H[x]<H[i]; x=maxr[x]);
        maxr[i]=x;
    }
    // maxl and maxr finds closest node greater than it to left and right 

    vl res(n);
    // F(i, 0, n) cout << H[i] << " "; cout << endl;

    F(i, 0, n) {
        int l = maxl[i], r = maxr[i];
        int a = H[i] - spmin.query(l+1, i);
        int b = H[i] - spmin.query(i+1, r);
        res[i] = min(a, b);
    }
    // Somehow, res is now filled with like 
    // "Consider only the peaks of the array. Now, when we scan left/right until we hit another peak",
    // find the min item in both sides. 
    // Do above equation 
    // F(i, 0, n) cout << res[i] << " "; cout << endl;

    seg::build(res);
}
 
int max_towers(int L, int R, int D) {
  auto [ret, indices] = seg::query(L, R+1, D);
  if(!ret) return 1;
  auto [mn, mx] = indices;
  int sa = (spmin.query(L, mn) > arr[mn] - D);
  int sb = (spmin.query(mx+1, R+1) > arr[mx] - D);
  
  return max(0, ret - sa - sb) + 1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 36944 KB Output is correct
2 Correct 712 ms 55756 KB Output is correct
3 Correct 691 ms 55888 KB Output is correct
4 Correct 693 ms 55888 KB Output is correct
5 Correct 679 ms 55888 KB Output is correct
6 Correct 681 ms 55652 KB Output is correct
7 Correct 670 ms 55888 KB Output is correct
8 Correct 3 ms 9816 KB Output is correct
9 Correct 5 ms 10840 KB Output is correct
10 Correct 4 ms 10840 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 571 ms 55496 KB 19th lines differ - on the 1st token, expected: '19863', found: '19864'
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 20576 KB Output is correct
2 Correct 771 ms 55756 KB Output is correct
3 Correct 717 ms 55736 KB Output is correct
4 Correct 705 ms 55760 KB Output is correct
5 Correct 714 ms 55740 KB Output is correct
6 Correct 735 ms 55704 KB Output is correct
7 Correct 669 ms 55752 KB Output is correct
8 Correct 565 ms 55888 KB Output is correct
9 Correct 626 ms 55816 KB Output is correct
10 Correct 645 ms 55760 KB Output is correct
11 Correct 593 ms 55888 KB Output is correct
12 Correct 68 ms 55888 KB Output is correct
13 Correct 67 ms 55756 KB Output is correct
14 Correct 67 ms 55888 KB Output is correct
15 Correct 63 ms 55752 KB Output is correct
16 Correct 59 ms 55760 KB Output is correct
17 Correct 66 ms 54204 KB Output is correct
18 Correct 74 ms 55756 KB Output is correct
19 Correct 69 ms 55784 KB Output is correct
20 Correct 66 ms 55852 KB Output is correct
21 Correct 66 ms 55704 KB Output is correct
22 Correct 68 ms 55864 KB Output is correct
23 Correct 66 ms 55888 KB Output is correct
24 Correct 61 ms 55756 KB Output is correct
25 Correct 57 ms 55888 KB Output is correct
26 Correct 59 ms 55752 KB Output is correct
27 Correct 62 ms 55752 KB Output is correct
28 Correct 5 ms 10840 KB Output is correct
29 Correct 4 ms 10840 KB Output is correct
30 Correct 4 ms 10840 KB Output is correct
31 Correct 5 ms 10840 KB Output is correct
32 Correct 5 ms 10840 KB Output is correct
33 Correct 4 ms 10328 KB Output is correct
34 Correct 4 ms 10840 KB Output is correct
35 Correct 5 ms 10840 KB Output is correct
36 Correct 4 ms 10840 KB Output is correct
37 Correct 7 ms 11096 KB Output is correct
38 Correct 5 ms 10840 KB Output is correct
39 Correct 5 ms 10840 KB Output is correct
40 Correct 4 ms 10840 KB Output is correct
41 Correct 4 ms 10840 KB Output is correct
42 Correct 4 ms 10840 KB Output is correct
43 Correct 5 ms 10840 KB Output is correct

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 36944 KB Output is correct
2 Correct 712 ms 55756 KB Output is correct
3 Correct 691 ms 55888 KB Output is correct
4 Correct 693 ms 55888 KB Output is correct
5 Correct 679 ms 55888 KB Output is correct
6 Correct 681 ms 55652 KB Output is correct
7 Correct 670 ms 55888 KB Output is correct
8 Correct 3 ms 9816 KB Output is correct
9 Correct 5 ms 10840 KB Output is correct
10 Correct 4 ms 10840 KB Output is correct
11 Incorrect 4 ms 10072 KB 1st lines differ - on the 1st token, expected: '13', found: '14'
12 Halted 0 ms 0 KB -