oj.uz

Submission #296463

# Submission time Handle Problem Language Result Execution time Memory
296463 2020-09-10T15:02:17 Z CaroLinda Strange Device (APIO19_strange_device) C++14
25 / 100
 1798 ms 288700 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("O2")

#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 ) ;

        ll actualL = ( (L+B)/B ) * B ;
        ll actualR = ( (R-B)/B ) * B + B-1 ;

        if(actualL - 1 >= L)
            vectorParciais.pb( mk(L, min(actualL-1, R) ) ) ;
        if(actualR+1 <= R)
            vectorParciais.pb( mk(max(L,actualR+1), R ) ) ;

        if( actualL > actualR ) continue ;

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

        actualL /= B ;
        actualR /= B ;

        actualL %= G ;
        actualR %= G ;

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

        vectorInteiros.pb( mk(actualL, actualR) ) ;

    }

    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 ) ;

}

Compilation message

strange_device.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
strange_device.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O2")
      | 
strange_device.cpp:47:25: warning: integer constant is so large that it is unsigned
   47 |     const ll period = ( 10000000000000000000LL / B < G ) ? 10000000000000000000LL : B*G ;
      |                         ^~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:47:60: warning: integer constant is so large that it is unsigned
   47 |     const ll period = ( 10000000000000000000LL / B < G ) ? 10000000000000000000LL : B*G ;
      |                                                            ^~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |     scanf("%d%lld%lld", &N , &A, &B ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         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 8 ms 1528 KB Output is correct
3 Correct 8 ms 1400 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Incorrect 1 ms 256 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
5.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 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1208 ms 163096 KB Output is correct
3 Incorrect 1798 ms 288700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1208 ms 163096 KB Output is correct
3 Incorrect 1798 ms 288700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1208 ms 163096 KB Output is correct
3 Incorrect 1798 ms 288700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 72 ms 10632 KB Output is correct
3 Correct 76 ms 10860 KB Output is correct
4 Correct 936 ms 113176 KB Output is correct
5 Correct 74 ms 12124 KB Output is correct
6 Correct 73 ms 11784 KB Output is correct
7 Correct 75 ms 12128 KB Output is correct
8 Correct 85 ms 14940 KB Output is correct
9 Correct 84 ms 14432 KB Output is correct
10 Correct 67 ms 10460 KB Output is correct
11 Correct 74 ms 10976 KB Output is correct
12 Correct 62 ms 10848 KB Output is correct
13 Correct 83 ms 13532 KB Output is correct
14 Correct 657 ms 70476 KB Output is correct
15 Correct 69 ms 11100 KB Output is correct
16 Correct 699 ms 70924 KB Output is correct
17 Correct 1049 ms 112204 KB Output is correct
18 Correct 1 ms 256 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 8 ms 1528 KB Output is correct
3 Correct 8 ms 1400 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Incorrect 1 ms 256 KB Output isn't correct
7 Halted 0 ms 0 KB -