oj.uz

Submission #701266

# Submission time Handle Problem Language Result Execution time Memory
701266 2023-02-20T17:03:48 Z boris_mihov Radio Towers (IOI22_towers) C++17
4 / 100
 883 ms 35932 KB 
#include "towers.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXLOG = 20;
const int INF  = 1e9;

int n;
int h[MAXN];
int perm[MAXN];
int getLog[MAXN];

struct Valley
{
    int idx;
    int left;
    int right;
};


struct SparseMAX
{
    int sparse[MAXLOG][MAXN];
    void build(const std::vector <int> &vals)
    {
        for (int i = 0 ; i < vals.size() ; ++i)
        {
            sparse[0][i] = vals[i];
        }

        for (int log = 1 ; (1 << log) < vals.size() ; ++log)
        {
            for (int i = 0 ; i + (1 << log) - 1 < vals.size() ; ++i)
            {
                sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
            }
        }

        for (int i = 1 ; i <= vals.size() ; ++i)
        {
            getLog[i] = getLog[i - 1];
            if ((1 << getLog[i] + 1) < i) getLog[i]++;
        }
    }

    inline int findMAX(int l, int r)
    {
        int log = getLog[r - l + 1];
        return std::max(sparse[log][l], sparse[log][r - (1 << log) + 1]);
    }
};

std::vector <Valley> valleys;
struct MergeSortTree
{
    std::vector <int> tree[4*MAXN];
    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node].push_back(std::min(valleys[l].left, valleys[l].right));
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);

        tree[node].reserve(r - l + 1);
        int lp = l, rp = mid + 1;
        for (int pos = l ; pos <= r ; ++pos)
        {
            if (lp == mid + 1)
            {
                tree[node].push_back(tree[2*node + 1][rp++]);
                continue;
            }

            if (rp == r + 1)
            {
                tree[node].push_back(tree[2*node][lp++]);
                continue;
            }

            if (tree[2*node][lp] > tree[2*node + 1][rp])
            {
                tree[node].push_back(tree[2*node][lp++]);
                continue;
            } else
            {
                tree[node].push_back(tree[2*node + 1][rp++]);
                continue;
            }
        }
    }

    inline int findBigger(int node, int value)
    {
        int l = -1, r = tree[node].size(), mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (tree[node][mid] >= value) l = mid;
            else r = mid;
        }

        return l + 1;
    }

    int query(int l, int r, int node, int queryL, int queryR, int queryVal)
    {
        if (queryL <= l && r <= queryR)
        {
            return findBigger(node, queryVal);
        }

        int ans = 0;
        int mid = (l + r) / 2;
        if (queryL <= mid) ans += query(l, mid, 2*node, queryL, queryR, queryVal);
        if (mid + 1 <= queryR) ans += query(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
        return ans;
    }

    void build()
    {
        build(0, valleys.size() - 1, 1);
    }

    int query(int l, int r, int val)
    {
        return query(0, valleys.size() - 1, 1, l, r, val);
    }
};

MergeSortTree tree;
int nextPeak[MAXN];
int prevPeak[MAXN];
bool isValley[MAXN];
int nextValley[MAXN];
int prevValley[MAXN];
SparseMAX leftMAX, rightMAX;
std::vector <int> extremums;
std::vector <int> peaks;

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

    for (int i = 1 ; i <= n ; ++i)
    {
        if (i == 1 || i == n || (h[i] < h[i - 1] && h[i] < h[i + 1])) extremums.push_back(i);
        else if (h[i] > h[i - 1] && h[i] > h[i + 1]) extremums.push_back(i);
    }
    
    for (int i = 0 ; i < extremums.size() ; ++i)
    {
        if (h[extremums[i]] > h[extremums[i] - 1] && h[extremums[i]] > h[extremums[i] + 1])
        {
            peaks.push_back(extremums[i]);
            continue;
        }

        int left = INF; 
        int right = INF; 
        if (i != 0) left = h[extremums[i - 1]] - h[extremums[i]];
        if (i != extremums.size() - 1) right = h[extremums[i + 1]] - h[extremums[i]];
        valleys.push_back({extremums[i], left, right});
        isValley[extremums[i]] = true;
    }

    std::fill(nextPeak + 1, nextPeak + 1 + n, -1);
    std::fill(prevPeak + 1, prevPeak + 1 + n, -1);
    std::fill(prevValley + 1, prevValley + 1 + n, -1);
    std::fill(nextValley + 1,nextValley + 1 + n, -1);

    int ptr = 1;
    for (int i = 0 ; i < valleys.size() ; ++i)
    {
        while (ptr < valleys[i].idx)
        {
            nextValley[ptr++] = i;
        }
    }

    ptr = 1;
    for (int i = 0 ; i < peaks.size() ; ++i)
    {
        while (ptr <= peaks[i])
        {
            nextPeak[ptr++] = i;
        }
    }

    ptr = n;
    for (int i = valleys.size() - 1 ; i >= 0 ; --i)
    {
        while (ptr > valleys[i].idx)
        {
            prevValley[ptr--] = i;
        }
    }

    ptr = n;
    for (int i = peaks.size() - 1 ; i >= 0 ; --i)
    {
        while (ptr >= peaks[i])
        {
            prevPeak[ptr--] = i;
        }
    }

    // std::cout << "valleys\n";
    // for (const Valley &v : valleys)
    // {
    //     std::cout << v.idx << ' ';
    // }

    // std::cout << '\n';

    // std::cout << "diffs\n";
    // for (const Valley &v : valleys)
    // {
    //     std::cout << v.left << ' ' << v.right << '\n';
    // }

    // std::cout << "peaks\n";
    // for (const int &idx : peaks)
    // {
    //     std::cout << idx << ' ';
    // }

    // std::cout << '\n';

    std::vector <int> curr;
    for (const Valley &v : valleys)
    {
        curr.push_back(v.left);
    }

    leftMAX.build(curr);
    curr.clear();
    
    for (const Valley &v : valleys)
    {
        curr.push_back(v.right);
    }

    rightMAX.build(curr);
    tree.build();
}

inline int findFirstRight(int from, int to, int d)
{
    int l = from - 1, r = to, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (rightMAX.findMAX(from, mid) < d) l = mid;
        else r = mid;
    }

    return r;
}

inline int findLastLeft(int from, int to, int d)
{
    int l = from, r = to + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (leftMAX.findMAX(mid, to) >= d) l = mid;
        else r = mid;
    }

    return l;
}

int max_towers(int l, int r, int d) 
{
    l++; r++;
    // std::cout << "l, r: " << l << ' ' << r << '\n';
    // std::cout << "here: " << nextPeak[l] << ' ' << nextPeak[r] << '\n';
    // std::cout << "here: " << nextValley[l] << ' ' << prevValley[r] << '\n';
    if (nextPeak[l] == nextPeak[r])
    {
        return 1;
    }

    int first = nextValley[l];
    int last = prevValley[r];
    // std::cout << "first last: " << first << ' ' << last << '\n';
    int borderL = -1;
    int borderR = -1;
    int answer = 0;

    if (h[l] < h[l + 1] && h[peaks[nextPeak[l]]] - h[l] >= d)
    {
        // std::cout << "L good\n";
        borderL = first;
        answer++;
    }

    if (h[r] < h[r - 1] && h[peaks[prevPeak[r]]] - h[r] >= d)
    {
        // std::cout << "R good\n";
        borderR = last;
        answer++;
    }

    if (borderL == -1)
    {
        if (first > last) return 1;
        borderL = findFirstRight(first, last, d);
        // std::cout << "borderL: " << valleys[borderL].idx << ' ' << valleys[borderL].right << ' ' << d << '\n';
        if (valleys[borderL].right < d) return 1;
        borderL++;
        answer++;
    }

    if (borderR == -1)
    {
        if (first > last) return 1;
        borderR = findLastLeft(first, last, d);
        if (valleys[borderR].left < d) return 1;
        borderR--;
        answer++;
    }
    
    // std::cout << "borders: " << borderL << ' ' << borderR << '\n';
    if (borderL <= borderR)
    {
        answer += tree.query(borderL, borderR, d);
    }

    return answer;
}

Compilation message

towers.cpp: In member function 'void SparseMAX::build(const std::vector<int>&)':
towers.cpp:31:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (int i = 0 ; i < vals.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~
towers.cpp:36:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int log = 1 ; (1 << log) < vals.size() ; ++log)
      |                            ~~~~~~~~~~~^~~~~~~~~~~~~
towers.cpp:38:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             for (int i = 0 ; i + (1 << log) - 1 < vals.size() ; ++i)
      |                              ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
towers.cpp:40:93: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |                 sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
      |                                                                                         ~~~~^~~
towers.cpp:44:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int i = 1 ; i <= vals.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~
towers.cpp:47:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   47 |             if ((1 << getLog[i] + 1) < i) getLog[i]++;
      |                       ~~~~~~~~~~^~~
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:164:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for (int i = 0 ; i < extremums.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~~~
towers.cpp:175:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |         if (i != extremums.size() - 1) right = h[extremums[i + 1]] - h[extremums[i]];
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:186:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Valley>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for (int i = 0 ; i < valleys.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~
towers.cpp:195:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |     for (int i = 0 ; i < peaks.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 11332 KB Output is correct
2 Correct 802 ms 12360 KB Output is correct
3 Correct 765 ms 12368 KB Output is correct
4 Correct 883 ms 12388 KB Output is correct
5 Correct 615 ms 12400 KB Output is correct
6 Correct 739 ms 12412 KB Output is correct
7 Correct 697 ms 12360 KB Output is correct
8 Correct 5 ms 9752 KB Output is correct
9 Correct 7 ms 9680 KB Output is correct
10 Correct 5 ms 9732 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 35932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 23500 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 11332 KB Output is correct
2 Correct 802 ms 12360 KB Output is correct
3 Correct 765 ms 12368 KB Output is correct
4 Correct 883 ms 12388 KB Output is correct
5 Correct 615 ms 12400 KB Output is correct
6 Correct 739 ms 12412 KB Output is correct
7 Correct 697 ms 12360 KB Output is correct
8 Correct 5 ms 9752 KB Output is correct
9 Correct 7 ms 9680 KB Output is correct
10 Correct 5 ms 9732 KB Output is correct
11 Incorrect 5 ms 9808 KB 1st lines differ - on the 1st token, expected: '13', found: '3'
12 Halted 0 ms 0 KB -