답안 #295286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295286	2020-09-09T15:03:46 Z	CaroLinda	새 집 (APIO18_new_home)	C++14	80 / 100	5000 ms	774320 KB

new_home

#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] ;
map< pii , int > segments[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:605:14:   required from here
new_home.cpp:564:9: warning: comparison of constant '0' with boolean expression is always false [-Wbool-compare]
  564 |   if (x < 0) {putchar('-'); x = -x; }
      |       ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:201:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  201 |     scanf("%d%d%d", &N , &K , &Q ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:205:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  205 |         scanf("%d%d%d%d", &x, &t, &a, &b ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:336:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  336 |         scanf("%d%d", &l, &y ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~
new_home.cpp:222:52: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
  222 |             int l = 0 , r = sz(compressionX) - 1 , mid ;
      |                                                    ^~~

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	42616 KB	Output is correct
2	Correct	30 ms	42624 KB	Output is correct
3	Correct	28 ms	42624 KB	Output is correct
4	Correct	30 ms	42752 KB	Output is correct
5	Correct	30 ms	42752 KB	Output is correct
6	Correct	32 ms	43136 KB	Output is correct
7	Correct	31 ms	43136 KB	Output is correct
8	Correct	31 ms	43008 KB	Output is correct
9	Correct	33 ms	43128 KB	Output is correct
10	Correct	31 ms	43028 KB	Output is correct
11	Correct	32 ms	43000 KB	Output is correct
12	Correct	32 ms	42880 KB	Output is correct
13	Correct	31 ms	42872 KB	Output is correct
14	Correct	31 ms	42872 KB	Output is correct
15	Correct	31 ms	43000 KB	Output is correct
16	Correct	31 ms	43008 KB	Output is correct
17	Correct	31 ms	42944 KB	Output is correct
18	Correct	32 ms	43008 KB	Output is correct
19	Correct	32 ms	43008 KB	Output is correct
20	Correct	31 ms	43000 KB	Output is correct
21	Correct	30 ms	42752 KB	Output is correct
22	Correct	32 ms	43132 KB	Output is correct
23	Correct	31 ms	43136 KB	Output is correct
24	Correct	31 ms	43008 KB	Output is correct
25	Correct	31 ms	43008 KB	Output is correct
26	Correct	32 ms	42880 KB	Output is correct
27	Correct	32 ms	42880 KB	Output is correct
28	Correct	35 ms	42872 KB	Output is correct
29	Correct	30 ms	42880 KB	Output is correct
30	Correct	31 ms	42904 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	42616 KB	Output is correct
2	Correct	30 ms	42624 KB	Output is correct
3	Correct	28 ms	42624 KB	Output is correct
4	Correct	30 ms	42752 KB	Output is correct
5	Correct	30 ms	42752 KB	Output is correct
6	Correct	32 ms	43136 KB	Output is correct
7	Correct	31 ms	43136 KB	Output is correct
8	Correct	31 ms	43008 KB	Output is correct
9	Correct	33 ms	43128 KB	Output is correct
10	Correct	31 ms	43028 KB	Output is correct
11	Correct	32 ms	43000 KB	Output is correct
12	Correct	32 ms	42880 KB	Output is correct
13	Correct	31 ms	42872 KB	Output is correct
14	Correct	31 ms	42872 KB	Output is correct
15	Correct	31 ms	43000 KB	Output is correct
16	Correct	31 ms	43008 KB	Output is correct
17	Correct	31 ms	42944 KB	Output is correct
18	Correct	32 ms	43008 KB	Output is correct
19	Correct	32 ms	43008 KB	Output is correct
20	Correct	31 ms	43000 KB	Output is correct
21	Correct	30 ms	42752 KB	Output is correct
22	Correct	32 ms	43132 KB	Output is correct
23	Correct	31 ms	43136 KB	Output is correct
24	Correct	31 ms	43008 KB	Output is correct
25	Correct	31 ms	43008 KB	Output is correct
26	Correct	32 ms	42880 KB	Output is correct
27	Correct	32 ms	42880 KB	Output is correct
28	Correct	35 ms	42872 KB	Output is correct
29	Correct	30 ms	42880 KB	Output is correct
30	Correct	31 ms	42904 KB	Output is correct
31	Correct	748 ms	141228 KB	Output is correct
32	Correct	105 ms	53000 KB	Output is correct
33	Correct	731 ms	135020 KB	Output is correct
34	Correct	729 ms	135120 KB	Output is correct
35	Correct	752 ms	140652 KB	Output is correct
36	Correct	759 ms	140456 KB	Output is correct
37	Correct	590 ms	125292 KB	Output is correct
38	Correct	593 ms	125248 KB	Output is correct
39	Correct	483 ms	110656 KB	Output is correct
40	Correct	501 ms	114760 KB	Output is correct
41	Correct	691 ms	121436 KB	Output is correct
42	Correct	672 ms	122208 KB	Output is correct
43	Correct	100 ms	50040 KB	Output is correct
44	Correct	674 ms	121508 KB	Output is correct
45	Correct	652 ms	112364 KB	Output is correct
46	Correct	570 ms	96588 KB	Output is correct
47	Correct	404 ms	95208 KB	Output is correct
48	Correct	370 ms	90932 KB	Output is correct
49	Correct	433 ms	101672 KB	Output is correct
50	Correct	507 ms	119384 KB	Output is correct
51	Correct	429 ms	97008 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2225 ms	395012 KB	Output is correct
2	Correct	2055 ms	374516 KB	Output is correct
3	Correct	2759 ms	574000 KB	Output is correct
4	Correct	2324 ms	427140 KB	Output is correct
5	Correct	2124 ms	387504 KB	Output is correct
6	Correct	2099 ms	382516 KB	Output is correct
7	Correct	2684 ms	584220 KB	Output is correct
8	Correct	2352 ms	424040 KB	Output is correct
9	Correct	2136 ms	377260 KB	Output is correct
10	Correct	2122 ms	366640 KB	Output is correct
11	Correct	1482 ms	348428 KB	Output is correct
12	Correct	1601 ms	385456 KB	Output is correct

Subtask #4

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3525 ms	488456 KB	Output is correct
2	Correct	408 ms	95564 KB	Output is correct
3	Correct	3505 ms	487684 KB	Output is correct
4	Correct	4056 ms	680572 KB	Output is correct
5	Correct	3590 ms	504060 KB	Output is correct
6	Correct	3688 ms	534916 KB	Output is correct
7	Correct	3628 ms	467108 KB	Output is correct
8	Correct	3669 ms	478864 KB	Output is correct
9	Correct	3936 ms	698240 KB	Output is correct
10	Correct	3866 ms	527660 KB	Output is correct
11	Correct	3805 ms	506084 KB	Output is correct
12	Correct	3477 ms	471648 KB	Output is correct
13	Correct	1992 ms	440708 KB	Output is correct
14	Correct	2019 ms	434920 KB	Output is correct
15	Correct	2302 ms	450696 KB	Output is correct
16	Correct	2581 ms	458180 KB	Output is correct
17	Correct	2555 ms	448424 KB	Output is correct

Subtask #5

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	42616 KB	Output is correct
2	Correct	30 ms	42624 KB	Output is correct
3	Correct	28 ms	42624 KB	Output is correct
4	Correct	30 ms	42752 KB	Output is correct
5	Correct	30 ms	42752 KB	Output is correct
6	Correct	32 ms	43136 KB	Output is correct
7	Correct	31 ms	43136 KB	Output is correct
8	Correct	31 ms	43008 KB	Output is correct
9	Correct	33 ms	43128 KB	Output is correct
10	Correct	31 ms	43028 KB	Output is correct
11	Correct	32 ms	43000 KB	Output is correct
12	Correct	32 ms	42880 KB	Output is correct
13	Correct	31 ms	42872 KB	Output is correct
14	Correct	31 ms	42872 KB	Output is correct
15	Correct	31 ms	43000 KB	Output is correct
16	Correct	31 ms	43008 KB	Output is correct
17	Correct	31 ms	42944 KB	Output is correct
18	Correct	32 ms	43008 KB	Output is correct
19	Correct	32 ms	43008 KB	Output is correct
20	Correct	31 ms	43000 KB	Output is correct
21	Correct	30 ms	42752 KB	Output is correct
22	Correct	32 ms	43132 KB	Output is correct
23	Correct	31 ms	43136 KB	Output is correct
24	Correct	31 ms	43008 KB	Output is correct
25	Correct	31 ms	43008 KB	Output is correct
26	Correct	32 ms	42880 KB	Output is correct
27	Correct	32 ms	42880 KB	Output is correct
28	Correct	35 ms	42872 KB	Output is correct
29	Correct	30 ms	42880 KB	Output is correct
30	Correct	31 ms	42904 KB	Output is correct
31	Correct	748 ms	141228 KB	Output is correct
32	Correct	105 ms	53000 KB	Output is correct
33	Correct	731 ms	135020 KB	Output is correct
34	Correct	729 ms	135120 KB	Output is correct
35	Correct	752 ms	140652 KB	Output is correct
36	Correct	759 ms	140456 KB	Output is correct
37	Correct	590 ms	125292 KB	Output is correct
38	Correct	593 ms	125248 KB	Output is correct
39	Correct	483 ms	110656 KB	Output is correct
40	Correct	501 ms	114760 KB	Output is correct
41	Correct	691 ms	121436 KB	Output is correct
42	Correct	672 ms	122208 KB	Output is correct
43	Correct	100 ms	50040 KB	Output is correct
44	Correct	674 ms	121508 KB	Output is correct
45	Correct	652 ms	112364 KB	Output is correct
46	Correct	570 ms	96588 KB	Output is correct
47	Correct	404 ms	95208 KB	Output is correct
48	Correct	370 ms	90932 KB	Output is correct
49	Correct	433 ms	101672 KB	Output is correct
50	Correct	507 ms	119384 KB	Output is correct
51	Correct	429 ms	97008 KB	Output is correct
52	Correct	891 ms	170024 KB	Output is correct
53	Correct	825 ms	159256 KB	Output is correct
54	Correct	791 ms	150252 KB	Output is correct
55	Correct	696 ms	133616 KB	Output is correct
56	Correct	690 ms	137100 KB	Output is correct
57	Correct	703 ms	124372 KB	Output is correct
58	Correct	770 ms	138452 KB	Output is correct
59	Correct	747 ms	146396 KB	Output is correct
60	Correct	751 ms	127316 KB	Output is correct
61	Correct	193 ms	64108 KB	Output is correct
62	Correct	789 ms	165348 KB	Output is correct
63	Correct	803 ms	156892 KB	Output is correct
64	Correct	798 ms	153184 KB	Output is correct
65	Correct	742 ms	143620 KB	Output is correct
66	Correct	702 ms	127580 KB	Output is correct
67	Correct	242 ms	74452 KB	Output is correct

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	42616 KB	Output is correct
2	Correct	30 ms	42624 KB	Output is correct
3	Correct	28 ms	42624 KB	Output is correct
4	Correct	30 ms	42752 KB	Output is correct
5	Correct	30 ms	42752 KB	Output is correct
6	Correct	32 ms	43136 KB	Output is correct
7	Correct	31 ms	43136 KB	Output is correct
8	Correct	31 ms	43008 KB	Output is correct
9	Correct	33 ms	43128 KB	Output is correct
10	Correct	31 ms	43028 KB	Output is correct
11	Correct	32 ms	43000 KB	Output is correct
12	Correct	32 ms	42880 KB	Output is correct
13	Correct	31 ms	42872 KB	Output is correct
14	Correct	31 ms	42872 KB	Output is correct
15	Correct	31 ms	43000 KB	Output is correct
16	Correct	31 ms	43008 KB	Output is correct
17	Correct	31 ms	42944 KB	Output is correct
18	Correct	32 ms	43008 KB	Output is correct
19	Correct	32 ms	43008 KB	Output is correct
20	Correct	31 ms	43000 KB	Output is correct
21	Correct	30 ms	42752 KB	Output is correct
22	Correct	32 ms	43132 KB	Output is correct
23	Correct	31 ms	43136 KB	Output is correct
24	Correct	31 ms	43008 KB	Output is correct
25	Correct	31 ms	43008 KB	Output is correct
26	Correct	32 ms	42880 KB	Output is correct
27	Correct	32 ms	42880 KB	Output is correct
28	Correct	35 ms	42872 KB	Output is correct
29	Correct	30 ms	42880 KB	Output is correct
30	Correct	31 ms	42904 KB	Output is correct
31	Correct	748 ms	141228 KB	Output is correct
32	Correct	105 ms	53000 KB	Output is correct
33	Correct	731 ms	135020 KB	Output is correct
34	Correct	729 ms	135120 KB	Output is correct
35	Correct	752 ms	140652 KB	Output is correct
36	Correct	759 ms	140456 KB	Output is correct
37	Correct	590 ms	125292 KB	Output is correct
38	Correct	593 ms	125248 KB	Output is correct
39	Correct	483 ms	110656 KB	Output is correct
40	Correct	501 ms	114760 KB	Output is correct
41	Correct	691 ms	121436 KB	Output is correct
42	Correct	672 ms	122208 KB	Output is correct
43	Correct	100 ms	50040 KB	Output is correct
44	Correct	674 ms	121508 KB	Output is correct
45	Correct	652 ms	112364 KB	Output is correct
46	Correct	570 ms	96588 KB	Output is correct
47	Correct	404 ms	95208 KB	Output is correct
48	Correct	370 ms	90932 KB	Output is correct
49	Correct	433 ms	101672 KB	Output is correct
50	Correct	507 ms	119384 KB	Output is correct
51	Correct	429 ms	97008 KB	Output is correct
52	Correct	2225 ms	395012 KB	Output is correct
53	Correct	2055 ms	374516 KB	Output is correct
54	Correct	2759 ms	574000 KB	Output is correct
55	Correct	2324 ms	427140 KB	Output is correct
56	Correct	2124 ms	387504 KB	Output is correct
57	Correct	2099 ms	382516 KB	Output is correct
58	Correct	2684 ms	584220 KB	Output is correct
59	Correct	2352 ms	424040 KB	Output is correct
60	Correct	2136 ms	377260 KB	Output is correct
61	Correct	2122 ms	366640 KB	Output is correct
62	Correct	1482 ms	348428 KB	Output is correct
63	Correct	1601 ms	385456 KB	Output is correct
64	Correct	3525 ms	488456 KB	Output is correct
65	Correct	408 ms	95564 KB	Output is correct
66	Correct	3505 ms	487684 KB	Output is correct
67	Correct	4056 ms	680572 KB	Output is correct
68	Correct	3590 ms	504060 KB	Output is correct
69	Correct	3688 ms	534916 KB	Output is correct
70	Correct	3628 ms	467108 KB	Output is correct
71	Correct	3669 ms	478864 KB	Output is correct
72	Correct	3936 ms	698240 KB	Output is correct
73	Correct	3866 ms	527660 KB	Output is correct
74	Correct	3805 ms	506084 KB	Output is correct
75	Correct	3477 ms	471648 KB	Output is correct
76	Correct	1992 ms	440708 KB	Output is correct
77	Correct	2019 ms	434920 KB	Output is correct
78	Correct	2302 ms	450696 KB	Output is correct
79	Correct	2581 ms	458180 KB	Output is correct
80	Correct	2555 ms	448424 KB	Output is correct
81	Correct	891 ms	170024 KB	Output is correct
82	Correct	825 ms	159256 KB	Output is correct
83	Correct	791 ms	150252 KB	Output is correct
84	Correct	696 ms	133616 KB	Output is correct
85	Correct	690 ms	137100 KB	Output is correct
86	Correct	703 ms	124372 KB	Output is correct
87	Correct	770 ms	138452 KB	Output is correct
88	Correct	747 ms	146396 KB	Output is correct
89	Correct	751 ms	127316 KB	Output is correct
90	Correct	193 ms	64108 KB	Output is correct
91	Correct	789 ms	165348 KB	Output is correct
92	Correct	803 ms	156892 KB	Output is correct
93	Correct	798 ms	153184 KB	Output is correct
94	Correct	742 ms	143620 KB	Output is correct
95	Correct	702 ms	127580 KB	Output is correct
96	Correct	242 ms	74452 KB	Output is correct
97	Execution timed out	5098 ms	774320 KB	Time limit exceeded
98	Halted	0 ms	0 KB	-