oj.uz

Submission #633460

# Submission time Handle Problem Language Result Execution time Memory
633460 2022-08-22T13:54:55 Z Lawliet Radio Towers (IOI22_towers) C++17
0 / 100
 933 ms 28192 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++)
    {
        cL[ optR[i] ] = max( cL[ optR[i] ] , 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 430 ms 16248 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 1 ms 464 KB Output is correct
2 Correct 1 ms 848 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 848 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 1 ms 464 KB Output is correct
2 Correct 1 ms 848 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 848 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 586 ms 27968 KB Output is correct
2 Correct 852 ms 28060 KB Output is correct
3 Correct 848 ms 28048 KB Output is correct
4 Correct 850 ms 28064 KB Output is correct
5 Correct 750 ms 28108 KB Output is correct
6 Correct 566 ms 28144 KB Output is correct
7 Correct 897 ms 28148 KB Output is correct
8 Correct 677 ms 28192 KB Output is correct
9 Correct 768 ms 28072 KB Output is correct
10 Correct 678 ms 28056 KB Output is correct
11 Correct 933 ms 28068 KB Output is correct
12 Incorrect 720 ms 28080 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 284 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 1 ms 464 KB Output is correct
2 Correct 1 ms 848 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 848 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 430 ms 16248 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -