oj.uz

Submission #633461

# Submission time Handle Problem Language Result Execution time Memory
633461 2022-08-22T13:57:07 Z Lawliet Radio Towers (IOI22_towers) C++17
0 / 100
 986 ms 28216 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];

bool hasBuilt = false;

SparseTable stV, stR, stL, corner;

vector<int> valleys, optL, optR, cL, cR;

bool isValid(int i, int j, int D)
{
    int peak = stV.query( i + 1 , j - 1 );

    if( v[i] <= peak - D && v[j] <= peak - D )
        return true;

    return false;
}

int findOptL(int i, int D)
{
    int l = 1, r = i - 1;

    if( v[i] > stV.query( l , i - 1 ) - D )
        return 0;

    while( l < r )
    {
        int m = ( l + r )/2;
        if( l == r - 1 ) m = r;

        if( v[i] <= stV.query( m , i - 1 ) - D )
            l = m;
        else
            r = m - 1;
    }

    return l;
}

int findOptR(int i, int D)
{
    int l = i + 1, r = n;

    if( v[i] > stV.query( i + 1 , r ) - D )
        return n + 1;

    while( l < r )
    {
        int m = ( l + r )/2;

        if( v[i] <= stV.query( i + 1 , m ) - D )
            r = m;
        else
            l = m + 1;
    }

    return r;
}

void buildHistogram(int D)
{
    optL.resize( n + 1 );
    optR.resize( n + 1 );

    for(int i = 1 ; i <= n ; i++)
    {
        optL[i] = findOptL(i, D);
        optR[i] = findOptR(i, D);
    }
}

void build(int D)
{
    buildHistogram(D);

    stR.build( n , optR , true );
    stL.build( n , optL );

    // Corner Case

    cL.resize( n + 1 , 0 );
    cR.resize( n + 1 , n + 1 );

    for(int i = 1 ; i <= n ; i++)
    {
        if( optR[i] <= n )
            cL[ optR[i] ] = max( cL[ optR[i] ] , i );

        if( 1 <= optL[i] )
            cR[ optL[i] ] = min( cR[ optL[i] ] , i );
    }

    vector<int> tmp(n + 1, n + 1);

    for(int i = 1 ; i <= n ; i++)
        tmp[ cL[i] ] = min( tmp[ cL[i] ] , cR[i] );

    corner.build( n , tmp );

    // 

    for(int i = 1 ; i <= n ; i++)
    {
        while( !valleys.empty() )
        {
            int j = valleys.back();

            if( isValid( j , i , D ) )
            {
                valleys.push_back( i );
                break;
            }

            if( v[j] < v[i] )
                break;

            valleys.pop_back();
        }

        if( valleys.empty() )
            valleys.push_back( i );
    }

    hasBuilt = true;
}

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

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

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

    stV.build( n , H );
}

bool newPairL(int L, int opt)
{
    int l = L, r = optL[opt] - 1;

    if( stR.query( l , r ) < opt )
        return true;

    return false;
}

bool newPairR(int R, int opt)
{
    int l = optR[opt] + 1, r = R;

    if( opt < stL.query( l , r ) )
        return true;

    return false;
}

int max_towers(int L, int R, int D) 
{
    if( !hasBuilt )
        build( D );

    L++; R++;

    if( R - L + 1 <= 2 )
        return 1;

    int pL = lower_bound( valleys.begin() , valleys.end() , L ) - valleys.begin();
    int pR = upper_bound( valleys.begin() , valleys.end() , R ) - valleys.begin();

    if( pL == pR )
    {
        if( corner.query( L , R ) <= R )
            return 2;

        return 1;
    }

    int ans = pR - pL;

    if( newPairL( L , valleys[pL] ) )
        ans++;

    if( newPairR( R , valleys[pR - 1] ) )
        ans++;

    return ans;
}

Subtask #1
0 / 4.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 1 ms 760 KB Output is correct
6 Correct 1 ms 848 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 848 KB Output is correct
11 Correct 1 ms 848 KB Output is correct
12 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 28024 KB Output is correct
2 Correct 879 ms 28084 KB Output is correct
3 Correct 917 ms 28088 KB Output is correct
4 Correct 982 ms 28216 KB Output is correct
5 Correct 869 ms 28100 KB Output is correct
6 Correct 986 ms 28092 KB Output is correct
7 Correct 865 ms 28076 KB Output is correct
8 Correct 778 ms 28052 KB Output is correct
9 Correct 677 ms 28116 KB Output is correct
10 Correct 718 ms 28052 KB Output is correct
11 Correct 805 ms 28080 KB Output is correct
12 Incorrect 877 ms 28092 KB 170th lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #7
0 / 23.0

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