oj.uz

Submission #296553

# Submission time Handle Problem Language Result Execution time Memory
296553 2020-09-10T16:07:08 Z CaroLinda Strange Device (APIO19_strange_device) C++14
35 / 100
 1601 ms 188840 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 7 ms 892 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 372 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 372 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 8 ms 1276 KB Output is correct
17 Correct 58 ms 4332 KB Output is correct
18 Incorrect 1 ms 256 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Incorrect 1 ms 256 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 516 ms 17288 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 975 ms 125792 KB Output is correct
3 Correct 651 ms 40892 KB Output is correct
4 Correct 653 ms 41116 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 975 ms 125792 KB Output is correct
3 Correct 651 ms 40892 KB Output is correct
4 Correct 653 ms 41116 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1522 ms 188500 KB Output is correct
7 Correct 763 ms 68540 KB Output is correct
8 Correct 1485 ms 188632 KB Output is correct
9 Correct 1601 ms 188792 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 975 ms 125792 KB Output is correct
3 Correct 651 ms 40892 KB Output is correct
4 Correct 653 ms 41116 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 118 ms 16348 KB Output is correct
7 Correct 142 ms 19528 KB Output is correct
8 Correct 139 ms 19532 KB Output is correct
9 Correct 145 ms 19684 KB Output is correct
10 Correct 103 ms 13404 KB Output is correct
11 Correct 140 ms 19536 KB Output is correct
12 Correct 139 ms 19528 KB Output is correct
13 Correct 147 ms 19548 KB Output is correct
14 Correct 64 ms 4452 KB Output is correct
15 Correct 131 ms 16604 KB Output is correct
16 Correct 59 ms 4484 KB Output is correct
17 Correct 143 ms 19676 KB Output is correct
18 Correct 1523 ms 188648 KB Output is correct
19 Correct 1475 ms 188840 KB Output is correct
20 Correct 1576 ms 188780 KB Output is correct
21 Correct 144 ms 19656 KB Output is correct
22 Correct 140 ms 19536 KB Output is correct
23 Correct 235 ms 9120 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 57 ms 4196 KB Output is correct
3 Correct 59 ms 4072 KB Output is correct
4 Correct 878 ms 85932 KB Output is correct
5 Correct 63 ms 5476 KB Output is correct
6 Correct 65 ms 5324 KB Output is correct
7 Correct 66 ms 5476 KB Output is correct
8 Correct 76 ms 7012 KB Output is correct
9 Correct 72 ms 7128 KB Output is correct
10 Correct 55 ms 3812 KB Output is correct
11 Correct 57 ms 4068 KB Output is correct
12 Correct 52 ms 4068 KB Output is correct
13 Correct 68 ms 6512 KB Output is correct
14 Correct 552 ms 32584 KB Output is correct
15 Correct 57 ms 4452 KB Output is correct
16 Correct 555 ms 33212 KB Output is correct
17 Correct 863 ms 80940 KB Output is correct
18 Incorrect 1 ms 256 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 7 ms 892 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 372 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 372 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 8 ms 1276 KB Output is correct
17 Correct 58 ms 4332 KB Output is correct
18 Incorrect 1 ms 256 KB Output isn't correct