oj.uz

Submission #633469

# Submission time Handle Problem Language Result Execution time Memory
633469 2022-08-22T14:08:31 Z Lawliet Radio Towers (IOI22_towers) C++17
0 / 100
 541 ms 8100 KB 
#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

const int maxl = 20;
const int maxn = 100010;
const int inf = 1000000010;

class SparseTable
{
    public:

        void build(int n, vector<int> v, bool mn = false)
        {
            isMin = mn;

            for(int i = 1 ; i <= n ; i++)
                tab[0][i] = (mn ? -v[i] : v[i]);

            for(int k = 1 ; k < maxl ; k++)
                for(int i = 1 ; i + (1 << k) - 1 <= n ; i++)
                    tab[k][i] = max( tab[k - 1][i] , tab[k - 1][i + (1 << (k - 1))] ); 
        }

        int query(int l, int r)
        {
            if( l > r )
                return (isMin ? inf : -inf);

            int t = 31 - __builtin_clz(r - l + 1);
            int ans = max( tab[t][l] , tab[t][r - (1 << t) + 1] );

            return (isMin ? -ans : ans);
        }

    protected:

        bool isMin;
        int tab[maxl][maxn];
};

int n;

int v[maxn];

SparseTable stV;

vector<int> ans;
vector<int> valleys;

void findValleys()
{
    v[0] = v[n + 1] = inf;

    for(int i = 1 ; i <= n ; i++)
        if( v[i - 1] > v[i] && v[i] < v[i + 1] ) valleys.push_back( i );

    for(int i = 0 ; i < (int)valleys.size() - 1 ; i++)
    {
        int peak = stV.query( valleys[i] + 1 , valleys[i + 1] - 1 );
        int diff = min( peak - v[ valleys[i] ] , peak - v[ valleys[i + 1] ] );

        ans.push_back( diff );
    }
}

void init(int N, vector<int> H) {
    n = N;

    H.insert( H.begin() , 0 );

    stV.build( n , H );

    for(int i = 1 ; i <= n ; i++)
        v[i] = H[i];

    findValleys();
}

int max_towers(int L, int R, int D) 
{
    int t = upper_bound( ans.begin() , ans.end() , D ) - ans.begin();
    return t + 1;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 237 ms 2000 KB 1st lines differ - on the 1st token, expected: '7197', found: '1002'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

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