oj.uz

Submission #296480

# Submission time Handle Problem Language Result Execution time Memory
296480 2020-09-10T15:12:13 Z CaroLinda Strange Device (APIO19_strange_device) C++14
35 / 100
 1808 ms 288280 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 ) ;

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

        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 ;

        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 7 ms 1400 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 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 1528 KB Output is correct
17 Correct 73 ms 11228 KB Output is correct
18 Incorrect 0 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 0 ms 256 KB Output is correct
3 Correct 0 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 1 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 677 ms 127208 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1198 ms 159576 KB Output is correct
3 Correct 1808 ms 284568 KB Output is correct
4 Correct 1798 ms 288280 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1198 ms 159576 KB Output is correct
3 Correct 1808 ms 284568 KB Output is correct
4 Correct 1798 ms 288280 KB Output is correct
5 Correct 0 ms 288 KB Output is correct
6 Correct 1450 ms 194236 KB Output is correct
7 Correct 953 ms 116448 KB Output is correct
8 Correct 1484 ms 199832 KB Output is correct
9 Correct 1593 ms 199988 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1198 ms 159576 KB Output is correct
3 Correct 1808 ms 284568 KB Output is correct
4 Correct 1798 ms 288280 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 114 ms 19676 KB Output is correct
7 Correct 142 ms 23132 KB Output is correct
8 Correct 135 ms 22876 KB Output is correct
9 Correct 145 ms 22876 KB Output is correct
10 Correct 105 ms 17116 KB Output is correct
11 Correct 137 ms 22888 KB Output is correct
12 Correct 136 ms 22848 KB Output is correct
13 Correct 145 ms 22876 KB Output is correct
14 Correct 81 ms 11484 KB Output is correct
15 Correct 127 ms 19872 KB Output is correct
16 Correct 70 ms 11356 KB Output is correct
17 Correct 137 ms 22876 KB Output is correct
18 Correct 1468 ms 199800 KB Output is correct
19 Correct 1454 ms 199828 KB Output is correct
20 Correct 1585 ms 199872 KB Output is correct
21 Correct 139 ms 22876 KB Output is correct
22 Correct 141 ms 23000 KB Output is correct
23 Correct 304 ms 57324 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 66 ms 9100 KB Output is correct
3 Correct 70 ms 9184 KB Output is correct
4 Correct 911 ms 109284 KB Output is correct
5 Correct 73 ms 10588 KB Output is correct
6 Correct 71 ms 10168 KB Output is correct
7 Correct 74 ms 10716 KB Output is correct
8 Correct 87 ms 13276 KB Output is correct
9 Correct 83 ms 13020 KB Output is correct
10 Correct 65 ms 9008 KB Output is correct
11 Correct 75 ms 9440 KB Output is correct
12 Correct 66 ms 9308 KB Output is correct
13 Correct 88 ms 12084 KB Output is correct
14 Correct 650 ms 66200 KB Output is correct
15 Correct 71 ms 9564 KB Output is correct
16 Correct 694 ms 66756 KB Output is correct
17 Correct 984 ms 107928 KB Output is correct
18 Incorrect 0 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 8 ms 1528 KB Output is correct
3 Correct 7 ms 1400 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 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 1528 KB Output is correct
17 Correct 73 ms 11228 KB Output is correct
18 Incorrect 0 ms 256 KB Output isn't correct