Submission #296553

#	Time	Username	Problem	Language	Result	Execution time	Memory
296553		CaroLinda	Strange Device (APIO19_strange_device)	C++14	35 / 100	1601 ms	188840 KiB

strange_device

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define debug //printf
#define tiii tuple<int,int,int>
#define mkt make_tuple
#define pii pair<int,int>
#define mk make_pair
#define ll long long
#define ff first
#define ss second

using namespace std ;

int N ;
ll A , B , G , ans ;
vector< pair<ll,ll> > vectorInteiros , vectorParciais , intervalosInteiros ;
map< ll , vector< pair<ll,ll> > > miniLineSweep ;

bool pegueiInteiro(ll block)
{

    auto it = upper_bound( all(intervalosInteiros) , mk(block,G+5) ) ;

    if( it == intervalosInteiros.begin() ) return false ;
    it-- ;

    return (it->ff <= block && it->ss >= block) ;

}

int main()
{
    scanf("%d%lld%lld", &N , &A, &B ) ;

    G = __gcd(A,B+1);
    G = A/G ;

    const ll period = ( 10000000000000000000LL / B < G ) ? 10000000000000000000LL : B*G ;

    for(int i = 1 ; i <= N ; i++ )
    {
        ll L , R ;
        scanf("%lld %lld", &L , &R ) ;

        if(R - L + 1LL >= period )
        {
            printf("%lld\n" , period ) ;
            return 0 ;
        }

        if( L/B == R/B )
        {
            vectorParciais.pb( mk(L,R) );
            continue ;
        }

        if( L%B != 0 )
        {
            ll aux = (L+B)/B ;
            aux *= B ;
            vectorParciais.pb( mk(L , aux-1) ) ;
            L = aux ;
        }
        if( R % B != B-1 )
        {
            ll aux = ( R-B )/B ;
            aux *= B ;
            aux += B-1 ;

            vectorParciais.pb( mk(aux+1, R) ) ;

            R = aux ;

        }

        if( L > R ) continue ;

        L /= B ;
        R /= B ;

        L %= G ;
        R %= G ;

        if( L > R )
        {
            vectorInteiros.pb( mk(L, G-1) ) ;
            L = 0 ;
        }

        vectorInteiros.pb(mk(L,R)) ;

    }

    for(auto e : vectorParciais ) debug("%lld %lld\n" , e.ff, e.ss ) ;


    if( sz(vectorInteiros) > 0 )
    {
        sort(all(vectorInteiros)) ;

        ll mn = vectorInteiros[0].ff ;
        ll mx = vectorInteiros[0].ss ;

        vectorInteiros.pb( mk(G+5, G+5) ) ;

        for(int i = 1 ; i < sz(vectorInteiros) ; i++ )
        {
            if( vectorInteiros[i].ff > mx )
            {

                intervalosInteiros.pb( mk(mn,mx) ) ;

                ans += (mx - mn + 1LL ) * B ;

                mn = vectorInteiros[i].ff ;
                mx = vectorInteiros[i].ss ;

            }
            else if( vectorInteiros[i].ss > mx ) mx = vectorInteiros[i].ss ;
        }

    }

    for(auto e : vectorParciais )
    {
        ll L = e.ff ;
        ll R = e.ss ;

        ll block = L/B ;
        block %= G ;

        L %= B ;
        R %= B ;

        miniLineSweep[ block ].pb( mk(L,R) ) ;

    }

    for(auto block : miniLineSweep )
    {

        if( pegueiInteiro(block.ff) ) continue ;

        debug("Estou vendo o modulo %d, e tenho nele:\n" , block.ff ) ;

        vector< pair<ll,ll> > &sweep = block.ss ;
        sort(all(sweep)) ;

        for(auto e :sweep ) debug("%lld %lld\n" ,e.ff, e.ss ) ;
        debug("\n") ;

        ll mn = sweep[0].ff ;
        ll mx = sweep[0].ss ;

        sweep.pb( mk(B+5, B+5) ) ;

        for(int i = 1 ;i  < sz(sweep) ; i++ )
        {

            if(sweep[i].ff > mx )
            {
                ans += mx - mn + 1LL ;
                mn = sweep[i].ff ;
                mx = sweep[i].ss ;
            }
            else if( mx < sweep[i].ss ) mx = sweep[i].ss ;

        }

    }

    printf("%lld\n" , ans ) ;

}

/*
2 5 10
10 19
40 59
*/

Compilation message (stderr)

strange_device.cpp:42:25: warning: integer constant is so large that it is unsigned
   42 |     const ll period = ( 10000000000000000000LL / B < G ) ? 10000000000000000000LL : B*G ;
      |                         ^~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:42:60: warning: integer constant is so large that it is unsigned
   42 |     const ll period = ( 10000000000000000000LL / B < G ) ? 10000000000000000000LL : B*G ;
      |                                                            ^~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:98:41: warning: left operand of comma operator has no effect [-Wunused-value]
   98 |     for(auto e : vectorParciais ) debug("%lld %lld\n" , e.ff, e.ss ) ;
      |                                         ^~~~~~~~~~~~~
strange_device.cpp:13:12: warning: right operand of comma operator has no effect [-Wunused-value]
   13 | #define ff first
      |            ^
strange_device.cpp:98:59: note: in expansion of macro 'ff'
   98 |     for(auto e : vectorParciais ) debug("%lld %lld\n" , e.ff, e.ss ) ;
      |                                                           ^~
strange_device.cpp:148:15: warning: left operand of comma operator has no effect [-Wunused-value]
  148 |         debug("Estou vendo o modulo %d, e tenho nele:\n" , block.ff ) ;
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:153:35: warning: left operand of comma operator has no effect [-Wunused-value]
  153 |         for(auto e :sweep ) debug("%lld %lld\n" ,e.ff, e.ss ) ;
      |                                   ^~~~~~~~~~~~~
strange_device.cpp:13:12: warning: right operand of comma operator has no effect [-Wunused-value]
   13 | #define ff first
      |            ^
strange_device.cpp:153:52: note: in expansion of macro 'ff'
  153 |         for(auto e :sweep ) debug("%lld %lld\n" ,e.ff, e.ss ) ;
      |                                                    ^~
strange_device.cpp:154:15: warning: statement has no effect [-Wunused-value]
  154 |         debug("\n") ;
      |              ~^~~~~
strange_device.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d%lld%lld", &N , &A, &B ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         scanf("%lld %lld", &L , &R ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30