oj.uz

Submission #295288

# Submission time Handle Problem Language Result Execution time Memory
295288 2020-09-09T15:05:06 Z CaroLinda New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 759568 KB 
#include <bits/stdc++.h>

static struct FASTIO {

  char READ_CHARACTER; bool REMAINING_CHARACTER = false;

  inline void ignore(); inline void flush();

  template <typename T> inline bool READ_INT(T &x); template <typename T> inline bool READ_STRING(T &x);
  /*                                                          Fast I/O Code Optimizer                                                          */
  template<size_t N> inline bool READ_CHAR_ARRAY(char (&x)[N]); template<size_t N> inline bool READ_VAR(char (&x)[N]);
  /*                    A tool to optimize execution time of C++ codes by replacing methods of reading and writing variables                   */
  template <typename T> inline bool READ_CHAR(T &x); inline bool READ_CHAR_ARRAY(char*& x); inline bool READ_GETLINE(std::string &x);
  /*                                                    Use it on fastio.pythonanywhere.com                                                    */
  template <typename T> inline bool READ_FLOAT(T &x); template <typename T> inline bool READ_DOUBLE(T &x);
  /*                                          Github Project: github.com/bfs07/Fast-IO-Code-Optimizer                                          */
  template<std::size_t N> inline bool READ_BITSET(std::bitset<N> &bit); template<std::size_t N> inline bool READ_VAR(std::bitset<N> &bit);
  inline bool READ_VAR(bool &x); inline bool READ_VAR(short int &x); inline bool READ_VAR(int &x); 
  inline bool READ_VAR(long int &x); inline bool READ_VAR(long long int &x); inline bool READ_VAR(unsigned short int &x);
  inline bool READ_VAR(unsigned int &x); inline bool READ_VAR(unsigned long &x); inline bool READ_VAR(unsigned long long &x);
  inline bool READ_VAR(std::string &x); inline bool READ_VAR(char &x); inline bool READ_VAR(char*& x); inline bool READ_VAR(float &x);
  inline bool READ_VAR(double &x); inline bool READ_VAR(long double &x); template <typename T> inline void WRITE_INT(T x);
  inline void WRITE_STRING(std::string &x); inline void WRITE_CHAR(char x); inline void WRITE_CHAR_ARRAY(const char *x);
  inline void WRITE_FLOAT(float x); template <typename T> inline void WRITE_DOUBLE(T x); inline void WRITE_VAR(bool x);
  inline void WRITE_VAR(short int x); inline void WRITE_VAR(int x); inline void WRITE_VAR(long int x); inline void WRITE_VAR(long long int x);
  inline void WRITE_VAR(unsigned short int x); inline void WRITE_VAR(unsigned int x); inline void WRITE_VAR(unsigned long x);
  inline void WRITE_VAR(unsigned long long x); inline void WRITE_VAR(char x); inline void WRITE_VAR(const char *x); 
  inline void WRITE_VAR(std::string &x); inline void WRITE_VAR(float x); inline void WRITE_VAR(double x); inline void WRITE_VAR(long double x);
  template<std::size_t N> inline void WRITE_VAR(std::bitset<N> &bit); template<std::size_t N> inline void WRITE_BITSET(std::bitset<N> &bit);

} __FIO__;


#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#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

const int MAXN = 3e5+10 ;
const int MAXT = 1e9+10 ;
const int MAX_COORD = 1e9+7 ;

using namespace std ;

struct Event
{
    int xConta, xIntercept, type , t1, t2 ;
    Event(int a=0, int b=0, int c=0, int d=0, int e=0) : xConta(a), xIntercept(b), type(c) , t1(d), t2(e){}

};

int ansQuery[MAXN] ;

struct Seg
{

    int n ;
    vector<Event> tree[MAXN*2] ;

    int m(int l, int r) { return (l+r)>>1 ; }

    void insertEvent(int t1, int t2,  Event e)
    {

        if(e.type > 0)
        {
            for(t1 += n ; t1 >= 1 ; t1 >>= 1)
                tree[t1].pb(e) ;

            return ;
        }

        for(t1 += n , t2 += n ; t1 < t2 ; t1 >>= 1 , t2>>=1 )
        {
            if( t1&1 ) tree[t1].pb(e), t1++ ;
            if( t2&1 ) t2--, tree[t2].pb(e) ;
        }

    }

    void solve(int forbiddenType )
    {
        for(int i = 1 ; i < 2*n ; i++ )
        {
            int mxNegative = -MAXT , mnPositive = MAXT ;

            for(auto e : tree[i])
            {
                if( e.type == forbiddenType ) continue ;
                if( e.type > 0 )
                {
                    int c = (forbiddenType == 0) ? mxNegative - e.xConta : e.xConta-mnPositive ;
                    if( ansQuery[e.type] < c ) ansQuery[e.type] = c ;
                }
                else
                {
                    if(forbiddenType == 0 && e.xIntercept > mxNegative ) mxNegative = e.xIntercept ;
                    else if( mnPositive > e.xIntercept) mnPositive = e.xIntercept ;
                }
            }
        }
    }

} seg ;


int N , K , Q ;
int timeRight[MAXN] , timeLeft[MAXN] , midRight[MAXN] ,midLeft[MAXN] ;
vector<int> compressionTime , compressionX ;
set<int> lojinhas ;
vector< pii > myVecOfPairs ;
vector<pii> coordX[MAXN] ;
vector<tiii> myStores[MAXN] ;
vector<Event> sweep ;

int maiorIgual(int x)
{

    int l = 0 , r = sz(compressionTime) - 1 , mid , best = r+1 ;

    while( l <= r )
    {
        mid = (l+r)>>1 ;
        if(compressionTime[mid] >= x)
        {
            best = mid ;
            r = mid - 1 ;
        }
        else l = mid + 1 ;
    }
    return best ;
}
int menorIgual(int x)
{
    int l = 0 , r = sz(compressionTime)-1 , mid , best = -1 ;

    while(l <= r)
    {
        mid = (l+r)>>1 ;
        if(compressionTime[mid] <= x )
        {
            best = mid ;
            l = mid + 1 ;
        }
        else r = mid - 1 ;
    }

    return best ;
}

void coloca(set<int>::iterator l , set<int>::iterator r , int t )
{

    int xl = compressionX[*l] ;
    int xr = compressionX[*r] ;

    midRight[*l] = (xr - xl)>>1 ;
    midRight[*l] += xl ;
    midLeft[*r] = ( (xr-xl)%2 == 0 ) ? midRight[*l] : ( midRight[*l]+1);

    timeRight[*l] = t ;
    timeLeft[*r] = t ;

}

void apaga( set<int>::iterator l , set<int>::iterator r , int t )
{

    int xl = compressionX[*l] ;
    int xr = compressionX[*r] ;

    if(timeRight[*l] <= t )
        sweep.pb( Event( midRight[*l] , xl , 0 , timeRight[*l] , t ) ) ;

    if(timeLeft[*r] <= t)
        sweep.pb( Event( midLeft[*r] , xr , -1, timeLeft[*r] , t ) ) ;

}


int main()
{

    scanf("%d%d%d", &N , &K , &Q ) ;

    for(int i = 1 , x , t , a , b ; i <= N ; i++ )
    {
        scanf("%d%d%d%d", &x, &t, &a, &b ) ;
        myStores[t].pb( mkt(x,a,b) ) ;
        compressionX.pb(x) ;
    }

    compressionX.pb(-MAXT) ;
    compressionX.pb(MAXT);
    sort(all(compressionX));
    compressionX.erase( unique( all(compressionX) ) , compressionX.end() ) ;

    for(int i = 1 ; i <= K ; i++ )
    {

        sort(all(myStores[i])) ;

        for(auto &tup : myStores[i])
        {
            int l = 0 , r = sz(compressionX) - 1 , mid ;

            while(l <= r)
            {
                mid = (l+r)>>1 ;

                if( compressionX[mid] == get<0>(tup) ) break ;
                else if( compressionX[mid] < get<0>(tup) ) l =mid+1 ;
                else r = mid - 1 ;
            }

            get<0>(tup) = mid ;
            coordX[mid].pb( mk(get<1>(tup) , get<2>(tup)) ) ;
        }

       for(int j = 0 ; j < sz(myStores[i]) ; j++ )
        {

            int X = get<0>(myStores[i][j]) ;

            if(j != 0 && X == get<0>(myStores[i][j-1]) ) continue ;

            int mnTime =  coordX[ X ][0].ff ;
            int mxTime =  coordX[ X ][0].ss ;
            coordX[X].pb( mk(MAXT, MAXT) ) ;

            for(int g = 1 ; g < sz( coordX[ X ] ) ; g++ )
            {
                if( coordX[X][g].ff > mxTime )
                {
                    myVecOfPairs.pb( mk( mnTime , -X ) ) ;
                    myVecOfPairs.pb( mk( mxTime , X ) ) ;

                    mnTime = coordX[X][g].ff ;
                    mxTime = coordX[X][g].ss ;
                }
                else if(coordX[X][g].ss > mxTime ) mxTime = coordX[X][g].ss ;
            }

            coordX[X].clear() ;

        }

         

        sort(all(myVecOfPairs)) ;

        lojinhas.insert(0) ;
        lojinhas.insert( sz(compressionX) - 1 ) ;

        coloca( lojinhas.begin() , prev( lojinhas.end() ) , 1 ) ;

        for(auto e : myVecOfPairs )
        {
            int t = e.ff ;
            int x = e.ss ;

            set<int>::iterator itMore , itLess;

            if(x < 0)
            {
                itMore = lojinhas.upper_bound(-x) ;
                itLess = itMore , itLess-- ;

                apaga(itLess, itMore, t-1) ;

                lojinhas.insert(-x) ;

                itMore = lojinhas.find(-x) ;
                itLess = itMore , itLess-- ;

                coloca(itLess, itMore , t) ;

                itLess = itMore , itLess++ ;
                swap(itLess, itMore) ;

                coloca(itLess, itMore, t) ;

            }
            else
            {
                itMore = lojinhas.find(x) ;
                itLess = itMore , itLess-- ;

                apaga(itLess, itMore , t ) ;


                itLess = itMore , itLess++ ;
                swap(itLess, itMore ) ;

                apaga(itLess, itMore, t ) ;

                lojinhas.erase(itLess) ;

                itMore = lojinhas.upper_bound(x) ;
                itLess = itMore , itLess-- ;

                coloca(itLess, itMore, t+1 ) ;

            }

        }

        apaga( lojinhas.begin() , prev(lojinhas.end() ) , MAXT ) ;

        myVecOfPairs.clear() ;
        lojinhas.clear() ;

    }

    

    for(int i = 1 , l , y ; i <= Q ; i++ )
    {
        scanf("%d%d", &l, &y ) ;
        sweep.pb( Event(l,l,i,y,y) );
        compressionTime.pb(y) ;
    }

     
    sort(all(compressionTime)) ;
    compressionTime.erase( unique(all(compressionTime)) , compressionTime.end() );
     

    sort(all(sweep), [&](Event a, Event b)
         {
             if( a.xConta != b.xConta ) return a.xConta < b.xConta ;
             else return a.type < b.type ;
         } );

    for(auto &e : sweep ) e.t1 = maiorIgual(e.t1) , e.t2 = menorIgual(e.t2) ;
    

    seg.n = sz(compressionTime) ;

    for(auto e : sweep )
        if( e.type != 0 && e.t1 <= e.t2 )
            seg.insertEvent( e.t1, e.t2+1 , e ) ;

    seg.solve( 0 ) ;

    sort(all(sweep), [&](Event a, Event b)
     {
         if( a.xConta != b.xConta ) return a.xConta > b.xConta ;
         else return a.type < b.type ;
     } );

    for(int i = 1 ; i < 2*seg.n ; i++ ) seg.tree[i].clear() ;

    for(auto e : sweep )
        if(e.type != -1 && e.t1 <= e.t2 )
            seg.insertEvent( e.t1, e.t2+1, e ) ;

    seg.solve( -1 ) ;

    for(int i = 1 ; i <= Q ; i++ ) printf("%d\n" , ansQuery[i] > 100000000 ? -1 : ansQuery[i] ) ;

}


#undef lp
#undef sz
#undef all
#undef lp
#undef pb
#undef sz
#undef all
#undef debug
#undef tiii
#undef mkt
#undef pii
#undef mk
#undef ll
#undef ff
#undef ss

inline void FASTIO::ignore() {
  if(REMAINING_CHARACTER == true) REMAINING_CHARACTER = false; else READ_CHARACTER = getchar();
}

inline void FASTIO::flush() {
  fflush(stdout);
}

// cin modifications

template <typename T>
inline bool FASTIO::READ_INT(T &x) {
  x = 0; T sig = 1;
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while (!isdigit(READ_CHARACTER) && READ_CHARACTER != EOF) sig = (READ_CHARACTER == '-' ? -sig : sig), READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while (isdigit(READ_CHARACTER)) x = x * 10 + READ_CHARACTER - '0', READ_CHARACTER = getchar();
  x *= sig; REMAINING_CHARACTER = true;
  return true;
}

template <typename T>
inline bool FASTIO::READ_STRING(T &x) {
  x = "";
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
  REMAINING_CHARACTER = true;
  return true;
}

inline bool FASTIO::READ_GETLINE(std::string &x) {
  x = "";
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
  REMAINING_CHARACTER = false;
  return true;
}

template <typename T>
inline bool FASTIO::READ_CHAR(T &x) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  x = READ_CHARACTER; REMAINING_CHARACTER = false;
  return true;
}


template<size_t N>
inline bool FASTIO::READ_CHAR_ARRAY(char (&x)[N]) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  char *ptr = &x[0];
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) *ptr++ = READ_CHARACTER, READ_CHARACTER = getchar();
  *ptr = '\0', REMAINING_CHARACTER = true;
  return true;
}

inline bool FASTIO::READ_CHAR_ARRAY(char*& x) {
  std::string y;
  if(READ_STRING(y) == false)
    return false;
  x = new char[(int)y.size() + 1];
  strcpy(x, y.c_str());
  return true;
}

template <typename T>
inline bool FASTIO::READ_FLOAT(T &x) {
  return (scanf("%f", &x) != EOF);
}

template <typename T>
inline bool FASTIO::READ_DOUBLE(T &x) {
  double y;
  if(scanf("%lf", &y) == EOF) return false;
  x = y;
  return true;
}

template<std::size_t N>
inline bool FASTIO::READ_BITSET(std::bitset<N> &x) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  int i = 0; REMAINING_CHARACTER = true;
  while (READ_CHARACTER == '0' || READ_CHARACTER == '1') x[i++] = READ_CHARACTER - '0', READ_CHARACTER = getchar();
  return true;
}

inline bool FASTIO::READ_VAR(short int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(long int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(long long int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned short int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned long &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned long long &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(std::string &x) {
  return READ_STRING(x);    
}

inline bool FASTIO::READ_VAR(char &x) {
  return READ_CHAR(x);
}

template<size_t N>
inline bool FASTIO::READ_VAR(char (&x)[N]) {
  return READ_CHAR_ARRAY(x);
}

inline bool FASTIO::READ_VAR(char*& x) {
  return READ_CHAR_ARRAY(x);
}

inline bool FASTIO::READ_VAR(float &x) {
  return READ_FLOAT(x);
}

inline bool FASTIO::READ_VAR(double &x) {
  return READ_DOUBLE(x);
}

inline bool FASTIO::READ_VAR(long double &x) {
  return READ_DOUBLE(x);
}

template<std::size_t N>
inline bool FASTIO::READ_VAR(std::bitset<N> &x) {
  return READ_BITSET(x);
}

// cout modifications

template <typename T>
inline void FASTIO::WRITE_INT(T x) {
  if (x < 0) {putchar('-'); x = -x; }
  char writeBuffer[20], *writePtr = writeBuffer;
  do {
    *writePtr++ = '0' + x % 10;
    x /= 10;
  }
  while (x);
  do  { putchar(*--writePtr); }
  while (writePtr > writeBuffer);
}

inline void FASTIO::WRITE_CHAR(char x) {
  putchar(x);
}

inline void FASTIO::WRITE_CHAR_ARRAY(const char *x) {
  while(*x != '\0')
    putchar(*x++);
}

inline void FASTIO::WRITE_STRING(std::string &x) {
  for(char c: x) 
    putchar(c);
}

inline void FASTIO::WRITE_FLOAT(float x) {
  printf("%f", x);
}

template <typename T>
inline void FASTIO::WRITE_DOUBLE(T x) {
  printf("%lf", (double)x);
}

template<std::size_t N>
inline void FASTIO::WRITE_BITSET(std::bitset<N> &x) {
  for(int i = (int)x.size() - 1; i >= 0; i--)
    putchar(x[i] + 48);
}

inline void FASTIO::WRITE_VAR(bool x) {
  WRITE_INT(x);
}

inline void FASTIO::WRITE_VAR(short int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(long int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(long long int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned short int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned long x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned long long x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(std::string &x) {
  WRITE_STRING(x);    
}

inline void FASTIO::WRITE_VAR(char x) {
  WRITE_CHAR(x);
}

inline void FASTIO::WRITE_VAR(const char *x) {
  WRITE_CHAR_ARRAY(x);
}

inline void FASTIO::WRITE_VAR(float x) {
  WRITE_FLOAT(x);
}

inline void FASTIO::WRITE_VAR(double x) {
  WRITE_DOUBLE(x);
}

inline void FASTIO::WRITE_VAR(long double x) {
  WRITE_DOUBLE(x);
}

template<std::size_t N>
inline void FASTIO::WRITE_VAR(std::bitset<N> &x) {
  WRITE_BITSET(x);
}

Compilation message

new_home.cpp:37: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   37 | #pragma GCC optimization ("O3")
      | 
new_home.cpp:38: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   38 | #pragma GCC optimization ("unroll-loops")
      | 
new_home.cpp: In instantiation of 'void FASTIO::WRITE_INT(T) [with T = bool]':
new_home.cpp:600:14:   required from here
new_home.cpp:559:9: warning: comparison of constant '0' with boolean expression is always false [-Wbool-compare]
  559 |   if (x < 0) {putchar('-'); x = -x; }
      |       ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:198:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  198 |     scanf("%d%d%d", &N , &K , &Q ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:202:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  202 |         scanf("%d%d%d%d", &x, &t, &a, &b ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:333:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  333 |         scanf("%d%d", &l, &y ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~
new_home.cpp:219:52: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
  219 |             int l = 0 , r = sz(compressionX) - 1 , mid ;
      |                                                    ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28544 KB Output is correct
2 Correct 20 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 19 ms 28544 KB Output is correct
5 Correct 34 ms 28664 KB Output is correct
6 Correct 22 ms 28928 KB Output is correct
7 Correct 29 ms 29056 KB Output is correct
8 Correct 22 ms 28920 KB Output is correct
9 Correct 26 ms 29056 KB Output is correct
10 Correct 22 ms 28928 KB Output is correct
11 Correct 25 ms 28824 KB Output is correct
12 Correct 23 ms 28800 KB Output is correct
13 Correct 23 ms 28800 KB Output is correct
14 Correct 24 ms 28800 KB Output is correct
15 Correct 22 ms 28928 KB Output is correct
16 Correct 23 ms 28928 KB Output is correct
17 Correct 23 ms 28928 KB Output is correct
18 Correct 23 ms 28920 KB Output is correct
19 Correct 27 ms 28920 KB Output is correct
20 Correct 22 ms 28928 KB Output is correct
21 Correct 21 ms 28664 KB Output is correct
22 Correct 23 ms 29056 KB Output is correct
23 Correct 23 ms 28940 KB Output is correct
24 Correct 23 ms 28960 KB Output is correct
25 Correct 21 ms 28928 KB Output is correct
26 Correct 21 ms 28800 KB Output is correct
27 Correct 22 ms 28800 KB Output is correct
28 Correct 22 ms 28792 KB Output is correct
29 Correct 20 ms 28800 KB Output is correct
30 Correct 20 ms 28800 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28544 KB Output is correct
2 Correct 20 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 19 ms 28544 KB Output is correct
5 Correct 34 ms 28664 KB Output is correct
6 Correct 22 ms 28928 KB Output is correct
7 Correct 29 ms 29056 KB Output is correct
8 Correct 22 ms 28920 KB Output is correct
9 Correct 26 ms 29056 KB Output is correct
10 Correct 22 ms 28928 KB Output is correct
11 Correct 25 ms 28824 KB Output is correct
12 Correct 23 ms 28800 KB Output is correct
13 Correct 23 ms 28800 KB Output is correct
14 Correct 24 ms 28800 KB Output is correct
15 Correct 22 ms 28928 KB Output is correct
16 Correct 23 ms 28928 KB Output is correct
17 Correct 23 ms 28928 KB Output is correct
18 Correct 23 ms 28920 KB Output is correct
19 Correct 27 ms 28920 KB Output is correct
20 Correct 22 ms 28928 KB Output is correct
21 Correct 21 ms 28664 KB Output is correct
22 Correct 23 ms 29056 KB Output is correct
23 Correct 23 ms 28940 KB Output is correct
24 Correct 23 ms 28960 KB Output is correct
25 Correct 21 ms 28928 KB Output is correct
26 Correct 21 ms 28800 KB Output is correct
27 Correct 22 ms 28800 KB Output is correct
28 Correct 22 ms 28792 KB Output is correct
29 Correct 20 ms 28800 KB Output is correct
30 Correct 20 ms 28800 KB Output is correct
31 Correct 820 ms 126608 KB Output is correct
32 Correct 96 ms 38144 KB Output is correct
33 Correct 771 ms 120412 KB Output is correct
34 Correct 761 ms 120692 KB Output is correct
35 Correct 808 ms 126436 KB Output is correct
36 Correct 799 ms 126272 KB Output is correct
37 Correct 608 ms 110860 KB Output is correct
38 Correct 595 ms 110912 KB Output is correct
39 Correct 484 ms 96448 KB Output is correct
40 Correct 509 ms 100264 KB Output is correct
41 Correct 681 ms 106972 KB Output is correct
42 Correct 701 ms 107744 KB Output is correct
43 Correct 98 ms 35576 KB Output is correct
44 Correct 684 ms 107116 KB Output is correct
45 Correct 659 ms 97720 KB Output is correct
46 Correct 567 ms 82352 KB Output is correct
47 Correct 396 ms 80740 KB Output is correct
48 Correct 369 ms 76472 KB Output is correct
49 Correct 438 ms 87148 KB Output is correct
50 Correct 508 ms 105048 KB Output is correct
51 Correct 438 ms 82672 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2419 ms 380184 KB Output is correct
2 Correct 2227 ms 360256 KB Output is correct
3 Correct 2912 ms 559852 KB Output is correct
4 Correct 2446 ms 412824 KB Output is correct
5 Correct 2194 ms 373292 KB Output is correct
6 Correct 2155 ms 368260 KB Output is correct
7 Correct 2716 ms 570164 KB Output is correct
8 Correct 2291 ms 409848 KB Output is correct
9 Correct 2289 ms 363020 KB Output is correct
10 Correct 2144 ms 352780 KB Output is correct
11 Correct 1506 ms 336280 KB Output is correct
12 Correct 1628 ms 373144 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3561 ms 480504 KB Output is correct
2 Correct 412 ms 83272 KB Output is correct
3 Correct 3511 ms 475488 KB Output is correct
4 Correct 4121 ms 669548 KB Output is correct
5 Correct 3587 ms 492552 KB Output is correct
6 Correct 3695 ms 523396 KB Output is correct
7 Correct 3652 ms 455500 KB Output is correct
8 Correct 3520 ms 467116 KB Output is correct
9 Correct 3760 ms 685292 KB Output is correct
10 Correct 3468 ms 511648 KB Output is correct
11 Correct 3521 ms 490452 KB Output is correct
12 Correct 3472 ms 457240 KB Output is correct
13 Correct 1995 ms 425556 KB Output is correct
14 Correct 1980 ms 421964 KB Output is correct
15 Correct 2263 ms 437948 KB Output is correct
16 Correct 2577 ms 445608 KB Output is correct
17 Correct 2581 ms 435920 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28544 KB Output is correct
2 Correct 20 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 19 ms 28544 KB Output is correct
5 Correct 34 ms 28664 KB Output is correct
6 Correct 22 ms 28928 KB Output is correct
7 Correct 29 ms 29056 KB Output is correct
8 Correct 22 ms 28920 KB Output is correct
9 Correct 26 ms 29056 KB Output is correct
10 Correct 22 ms 28928 KB Output is correct
11 Correct 25 ms 28824 KB Output is correct
12 Correct 23 ms 28800 KB Output is correct
13 Correct 23 ms 28800 KB Output is correct
14 Correct 24 ms 28800 KB Output is correct
15 Correct 22 ms 28928 KB Output is correct
16 Correct 23 ms 28928 KB Output is correct
17 Correct 23 ms 28928 KB Output is correct
18 Correct 23 ms 28920 KB Output is correct
19 Correct 27 ms 28920 KB Output is correct
20 Correct 22 ms 28928 KB Output is correct
21 Correct 21 ms 28664 KB Output is correct
22 Correct 23 ms 29056 KB Output is correct
23 Correct 23 ms 28940 KB Output is correct
24 Correct 23 ms 28960 KB Output is correct
25 Correct 21 ms 28928 KB Output is correct
26 Correct 21 ms 28800 KB Output is correct
27 Correct 22 ms 28800 KB Output is correct
28 Correct 22 ms 28792 KB Output is correct
29 Correct 20 ms 28800 KB Output is correct
30 Correct 20 ms 28800 KB Output is correct
31 Correct 820 ms 126608 KB Output is correct
32 Correct 96 ms 38144 KB Output is correct
33 Correct 771 ms 120412 KB Output is correct
34 Correct 761 ms 120692 KB Output is correct
35 Correct 808 ms 126436 KB Output is correct
36 Correct 799 ms 126272 KB Output is correct
37 Correct 608 ms 110860 KB Output is correct
38 Correct 595 ms 110912 KB Output is correct
39 Correct 484 ms 96448 KB Output is correct
40 Correct 509 ms 100264 KB Output is correct
41 Correct 681 ms 106972 KB Output is correct
42 Correct 701 ms 107744 KB Output is correct
43 Correct 98 ms 35576 KB Output is correct
44 Correct 684 ms 107116 KB Output is correct
45 Correct 659 ms 97720 KB Output is correct
46 Correct 567 ms 82352 KB Output is correct
47 Correct 396 ms 80740 KB Output is correct
48 Correct 369 ms 76472 KB Output is correct
49 Correct 438 ms 87148 KB Output is correct
50 Correct 508 ms 105048 KB Output is correct
51 Correct 438 ms 82672 KB Output is correct
52 Correct 865 ms 156116 KB Output is correct
53 Correct 849 ms 145348 KB Output is correct
54 Correct 818 ms 136264 KB Output is correct
55 Correct 695 ms 119480 KB Output is correct
56 Correct 685 ms 123460 KB Output is correct
57 Correct 714 ms 110652 KB Output is correct
58 Correct 761 ms 124432 KB Output is correct
59 Correct 782 ms 132516 KB Output is correct
60 Correct 744 ms 113552 KB Output is correct
61 Correct 218 ms 50788 KB Output is correct
62 Correct 875 ms 151568 KB Output is correct
63 Correct 851 ms 143116 KB Output is correct
64 Correct 812 ms 139396 KB Output is correct
65 Correct 754 ms 129892 KB Output is correct
66 Correct 748 ms 113880 KB Output is correct
67 Correct 242 ms 60624 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28544 KB Output is correct
2 Correct 20 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 19 ms 28544 KB Output is correct
5 Correct 34 ms 28664 KB Output is correct
6 Correct 22 ms 28928 KB Output is correct
7 Correct 29 ms 29056 KB Output is correct
8 Correct 22 ms 28920 KB Output is correct
9 Correct 26 ms 29056 KB Output is correct
10 Correct 22 ms 28928 KB Output is correct
11 Correct 25 ms 28824 KB Output is correct
12 Correct 23 ms 28800 KB Output is correct
13 Correct 23 ms 28800 KB Output is correct
14 Correct 24 ms 28800 KB Output is correct
15 Correct 22 ms 28928 KB Output is correct
16 Correct 23 ms 28928 KB Output is correct
17 Correct 23 ms 28928 KB Output is correct
18 Correct 23 ms 28920 KB Output is correct
19 Correct 27 ms 28920 KB Output is correct
20 Correct 22 ms 28928 KB Output is correct
21 Correct 21 ms 28664 KB Output is correct
22 Correct 23 ms 29056 KB Output is correct
23 Correct 23 ms 28940 KB Output is correct
24 Correct 23 ms 28960 KB Output is correct
25 Correct 21 ms 28928 KB Output is correct
26 Correct 21 ms 28800 KB Output is correct
27 Correct 22 ms 28800 KB Output is correct
28 Correct 22 ms 28792 KB Output is correct
29 Correct 20 ms 28800 KB Output is correct
30 Correct 20 ms 28800 KB Output is correct
31 Correct 820 ms 126608 KB Output is correct
32 Correct 96 ms 38144 KB Output is correct
33 Correct 771 ms 120412 KB Output is correct
34 Correct 761 ms 120692 KB Output is correct
35 Correct 808 ms 126436 KB Output is correct
36 Correct 799 ms 126272 KB Output is correct
37 Correct 608 ms 110860 KB Output is correct
38 Correct 595 ms 110912 KB Output is correct
39 Correct 484 ms 96448 KB Output is correct
40 Correct 509 ms 100264 KB Output is correct
41 Correct 681 ms 106972 KB Output is correct
42 Correct 701 ms 107744 KB Output is correct
43 Correct 98 ms 35576 KB Output is correct
44 Correct 684 ms 107116 KB Output is correct
45 Correct 659 ms 97720 KB Output is correct
46 Correct 567 ms 82352 KB Output is correct
47 Correct 396 ms 80740 KB Output is correct
48 Correct 369 ms 76472 KB Output is correct
49 Correct 438 ms 87148 KB Output is correct
50 Correct 508 ms 105048 KB Output is correct
51 Correct 438 ms 82672 KB Output is correct
52 Correct 2419 ms 380184 KB Output is correct
53 Correct 2227 ms 360256 KB Output is correct
54 Correct 2912 ms 559852 KB Output is correct
55 Correct 2446 ms 412824 KB Output is correct
56 Correct 2194 ms 373292 KB Output is correct
57 Correct 2155 ms 368260 KB Output is correct
58 Correct 2716 ms 570164 KB Output is correct
59 Correct 2291 ms 409848 KB Output is correct
60 Correct 2289 ms 363020 KB Output is correct
61 Correct 2144 ms 352780 KB Output is correct
62 Correct 1506 ms 336280 KB Output is correct
63 Correct 1628 ms 373144 KB Output is correct
64 Correct 3561 ms 480504 KB Output is correct
65 Correct 412 ms 83272 KB Output is correct
66 Correct 3511 ms 475488 KB Output is correct
67 Correct 4121 ms 669548 KB Output is correct
68 Correct 3587 ms 492552 KB Output is correct
69 Correct 3695 ms 523396 KB Output is correct
70 Correct 3652 ms 455500 KB Output is correct
71 Correct 3520 ms 467116 KB Output is correct
72 Correct 3760 ms 685292 KB Output is correct
73 Correct 3468 ms 511648 KB Output is correct
74 Correct 3521 ms 490452 KB Output is correct
75 Correct 3472 ms 457240 KB Output is correct
76 Correct 1995 ms 425556 KB Output is correct
77 Correct 1980 ms 421964 KB Output is correct
78 Correct 2263 ms 437948 KB Output is correct
79 Correct 2577 ms 445608 KB Output is correct
80 Correct 2581 ms 435920 KB Output is correct
81 Correct 865 ms 156116 KB Output is correct
82 Correct 849 ms 145348 KB Output is correct
83 Correct 818 ms 136264 KB Output is correct
84 Correct 695 ms 119480 KB Output is correct
85 Correct 685 ms 123460 KB Output is correct
86 Correct 714 ms 110652 KB Output is correct
87 Correct 761 ms 124432 KB Output is correct
88 Correct 782 ms 132516 KB Output is correct
89 Correct 744 ms 113552 KB Output is correct
90 Correct 218 ms 50788 KB Output is correct
91 Correct 875 ms 151568 KB Output is correct
92 Correct 851 ms 143116 KB Output is correct
93 Correct 812 ms 139396 KB Output is correct
94 Correct 754 ms 129892 KB Output is correct
95 Correct 748 ms 113880 KB Output is correct
96 Correct 242 ms 60624 KB Output is correct
97 Execution timed out 5111 ms 759568 KB Time limit exceeded
98 Halted 0 ms 0 KB -