답안 #295271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295271	2020-09-09T14:53:26 Z	CaroLinda	새 집 (APIO18_new_home)	C++14	80 / 100	5000 ms	773492 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 optimize("Ofast")
 
#pragma GCC optimize("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+100 ;
const int MAXT = 1e9+10 ;
const int MAX_COORD = 3e8+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 )
                {
                    ansQuery[ e.type ] = max( ansQuery[e.type] , (forbiddenType == 0) ? mxNegative - e.xConta : e.xConta-mnPositive ) ;
                }
                else
                {
                    if(forbiddenType == 0) mxNegative = max(mxNegative, e.xIntercept ) ;
                    else mnPositive = min(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 mxTime = max(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: 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	31 ms	42624 KB	Output is correct
2	Correct	29 ms	42624 KB	Output is correct
3	Correct	30 ms	42616 KB	Output is correct
4	Correct	29 ms	42624 KB	Output is correct
5	Correct	30 ms	42752 KB	Output is correct
6	Correct	32 ms	43000 KB	Output is correct
7	Correct	32 ms	43136 KB	Output is correct
8	Correct	31 ms	43128 KB	Output is correct
9	Correct	33 ms	43136 KB	Output is correct
10	Correct	32 ms	43008 KB	Output is correct
11	Correct	31 ms	43000 KB	Output is correct
12	Correct	31 ms	42880 KB	Output is correct
13	Correct	34 ms	42872 KB	Output is correct
14	Correct	31 ms	42880 KB	Output is correct
15	Correct	31 ms	43008 KB	Output is correct
16	Correct	31 ms	43008 KB	Output is correct
17	Correct	31 ms	43008 KB	Output is correct
18	Correct	31 ms	43000 KB	Output is correct
19	Correct	31 ms	43128 KB	Output is correct
20	Correct	33 ms	43000 KB	Output is correct
21	Correct	29 ms	42848 KB	Output is correct
22	Correct	32 ms	43136 KB	Output is correct
23	Correct	32 ms	43136 KB	Output is correct
24	Correct	32 ms	43136 KB	Output is correct
25	Correct	33 ms	43000 KB	Output is correct
26	Correct	32 ms	43064 KB	Output is correct
27	Correct	31 ms	42880 KB	Output is correct
28	Correct	32 ms	42880 KB	Output is correct
29	Correct	31 ms	42872 KB	Output is correct
30	Correct	31 ms	42880 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	42624 KB	Output is correct
2	Correct	29 ms	42624 KB	Output is correct
3	Correct	30 ms	42616 KB	Output is correct
4	Correct	29 ms	42624 KB	Output is correct
5	Correct	30 ms	42752 KB	Output is correct
6	Correct	32 ms	43000 KB	Output is correct
7	Correct	32 ms	43136 KB	Output is correct
8	Correct	31 ms	43128 KB	Output is correct
9	Correct	33 ms	43136 KB	Output is correct
10	Correct	32 ms	43008 KB	Output is correct
11	Correct	31 ms	43000 KB	Output is correct
12	Correct	31 ms	42880 KB	Output is correct
13	Correct	34 ms	42872 KB	Output is correct
14	Correct	31 ms	42880 KB	Output is correct
15	Correct	31 ms	43008 KB	Output is correct
16	Correct	31 ms	43008 KB	Output is correct
17	Correct	31 ms	43008 KB	Output is correct
18	Correct	31 ms	43000 KB	Output is correct
19	Correct	31 ms	43128 KB	Output is correct
20	Correct	33 ms	43000 KB	Output is correct
21	Correct	29 ms	42848 KB	Output is correct
22	Correct	32 ms	43136 KB	Output is correct
23	Correct	32 ms	43136 KB	Output is correct
24	Correct	32 ms	43136 KB	Output is correct
25	Correct	33 ms	43000 KB	Output is correct
26	Correct	32 ms	43064 KB	Output is correct
27	Correct	31 ms	42880 KB	Output is correct
28	Correct	32 ms	42880 KB	Output is correct
29	Correct	31 ms	42872 KB	Output is correct
30	Correct	31 ms	42880 KB	Output is correct
31	Correct	777 ms	142936 KB	Output is correct
32	Correct	109 ms	53256 KB	Output is correct
33	Correct	730 ms	136684 KB	Output is correct
34	Correct	736 ms	136912 KB	Output is correct
35	Correct	748 ms	142572 KB	Output is correct
36	Correct	757 ms	142188 KB	Output is correct
37	Correct	603 ms	127212 KB	Output is correct
38	Correct	600 ms	126948 KB	Output is correct
39	Correct	471 ms	112452 KB	Output is correct
40	Correct	505 ms	116332 KB	Output is correct
41	Correct	696 ms	123112 KB	Output is correct
42	Correct	698 ms	123872 KB	Output is correct
43	Correct	100 ms	51192 KB	Output is correct
44	Correct	701 ms	123116 KB	Output is correct
45	Correct	644 ms	114028 KB	Output is correct
46	Correct	576 ms	98372 KB	Output is correct
47	Correct	407 ms	96748 KB	Output is correct
48	Correct	381 ms	92600 KB	Output is correct
49	Correct	444 ms	103276 KB	Output is correct
50	Correct	504 ms	121176 KB	Output is correct
51	Correct	432 ms	98672 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2310 ms	397568 KB	Output is correct
2	Correct	2144 ms	377280 KB	Output is correct
3	Correct	2844 ms	575156 KB	Output is correct
4	Correct	2426 ms	427112 KB	Output is correct
5	Correct	2201 ms	387428 KB	Output is correct
6	Correct	2136 ms	382372 KB	Output is correct
7	Correct	2707 ms	584468 KB	Output is correct
8	Correct	2340 ms	423684 KB	Output is correct
9	Correct	2222 ms	376912 KB	Output is correct
10	Correct	2139 ms	366180 KB	Output is correct
11	Correct	1529 ms	348424 KB	Output is correct
12	Correct	1663 ms	385384 KB	Output is correct

Subtask #4

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3584 ms	489928 KB	Output is correct
2	Correct	419 ms	96840 KB	Output is correct
3	Correct	3525 ms	487324 KB	Output is correct
4	Correct	4212 ms	680692 KB	Output is correct
5	Correct	3666 ms	503592 KB	Output is correct
6	Correct	3804 ms	534604 KB	Output is correct
7	Correct	3880 ms	467440 KB	Output is correct
8	Correct	3871 ms	479092 KB	Output is correct
9	Correct	4214 ms	697788 KB	Output is correct
10	Correct	3613 ms	525844 KB	Output is correct
11	Correct	3580 ms	504528 KB	Output is correct
12	Correct	3475 ms	471044 KB	Output is correct
13	Correct	1973 ms	439568 KB	Output is correct
14	Correct	1956 ms	434188 KB	Output is correct
15	Correct	2227 ms	450192 KB	Output is correct
16	Correct	2508 ms	458120 KB	Output is correct
17	Correct	2428 ms	448336 KB	Output is correct

Subtask #5

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	42624 KB	Output is correct
2	Correct	29 ms	42624 KB	Output is correct
3	Correct	30 ms	42616 KB	Output is correct
4	Correct	29 ms	42624 KB	Output is correct
5	Correct	30 ms	42752 KB	Output is correct
6	Correct	32 ms	43000 KB	Output is correct
7	Correct	32 ms	43136 KB	Output is correct
8	Correct	31 ms	43128 KB	Output is correct
9	Correct	33 ms	43136 KB	Output is correct
10	Correct	32 ms	43008 KB	Output is correct
11	Correct	31 ms	43000 KB	Output is correct
12	Correct	31 ms	42880 KB	Output is correct
13	Correct	34 ms	42872 KB	Output is correct
14	Correct	31 ms	42880 KB	Output is correct
15	Correct	31 ms	43008 KB	Output is correct
16	Correct	31 ms	43008 KB	Output is correct
17	Correct	31 ms	43008 KB	Output is correct
18	Correct	31 ms	43000 KB	Output is correct
19	Correct	31 ms	43128 KB	Output is correct
20	Correct	33 ms	43000 KB	Output is correct
21	Correct	29 ms	42848 KB	Output is correct
22	Correct	32 ms	43136 KB	Output is correct
23	Correct	32 ms	43136 KB	Output is correct
24	Correct	32 ms	43136 KB	Output is correct
25	Correct	33 ms	43000 KB	Output is correct
26	Correct	32 ms	43064 KB	Output is correct
27	Correct	31 ms	42880 KB	Output is correct
28	Correct	32 ms	42880 KB	Output is correct
29	Correct	31 ms	42872 KB	Output is correct
30	Correct	31 ms	42880 KB	Output is correct
31	Correct	777 ms	142936 KB	Output is correct
32	Correct	109 ms	53256 KB	Output is correct
33	Correct	730 ms	136684 KB	Output is correct
34	Correct	736 ms	136912 KB	Output is correct
35	Correct	748 ms	142572 KB	Output is correct
36	Correct	757 ms	142188 KB	Output is correct
37	Correct	603 ms	127212 KB	Output is correct
38	Correct	600 ms	126948 KB	Output is correct
39	Correct	471 ms	112452 KB	Output is correct
40	Correct	505 ms	116332 KB	Output is correct
41	Correct	696 ms	123112 KB	Output is correct
42	Correct	698 ms	123872 KB	Output is correct
43	Correct	100 ms	51192 KB	Output is correct
44	Correct	701 ms	123116 KB	Output is correct
45	Correct	644 ms	114028 KB	Output is correct
46	Correct	576 ms	98372 KB	Output is correct
47	Correct	407 ms	96748 KB	Output is correct
48	Correct	381 ms	92600 KB	Output is correct
49	Correct	444 ms	103276 KB	Output is correct
50	Correct	504 ms	121176 KB	Output is correct
51	Correct	432 ms	98672 KB	Output is correct
52	Correct	819 ms	170196 KB	Output is correct
53	Correct	810 ms	159316 KB	Output is correct
54	Correct	789 ms	150176 KB	Output is correct
55	Correct	681 ms	133484 KB	Output is correct
56	Correct	669 ms	137068 KB	Output is correct
57	Correct	729 ms	124504 KB	Output is correct
58	Correct	717 ms	138332 KB	Output is correct
59	Correct	776 ms	146384 KB	Output is correct
60	Correct	720 ms	127320 KB	Output is correct
61	Correct	185 ms	64496 KB	Output is correct
62	Correct	788 ms	165332 KB	Output is correct
63	Correct	801 ms	156868 KB	Output is correct
64	Correct	778 ms	153180 KB	Output is correct
65	Correct	741 ms	143784 KB	Output is correct
66	Correct	692 ms	127576 KB	Output is correct
67	Correct	239 ms	74832 KB	Output is correct

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	42624 KB	Output is correct
2	Correct	29 ms	42624 KB	Output is correct
3	Correct	30 ms	42616 KB	Output is correct
4	Correct	29 ms	42624 KB	Output is correct
5	Correct	30 ms	42752 KB	Output is correct
6	Correct	32 ms	43000 KB	Output is correct
7	Correct	32 ms	43136 KB	Output is correct
8	Correct	31 ms	43128 KB	Output is correct
9	Correct	33 ms	43136 KB	Output is correct
10	Correct	32 ms	43008 KB	Output is correct
11	Correct	31 ms	43000 KB	Output is correct
12	Correct	31 ms	42880 KB	Output is correct
13	Correct	34 ms	42872 KB	Output is correct
14	Correct	31 ms	42880 KB	Output is correct
15	Correct	31 ms	43008 KB	Output is correct
16	Correct	31 ms	43008 KB	Output is correct
17	Correct	31 ms	43008 KB	Output is correct
18	Correct	31 ms	43000 KB	Output is correct
19	Correct	31 ms	43128 KB	Output is correct
20	Correct	33 ms	43000 KB	Output is correct
21	Correct	29 ms	42848 KB	Output is correct
22	Correct	32 ms	43136 KB	Output is correct
23	Correct	32 ms	43136 KB	Output is correct
24	Correct	32 ms	43136 KB	Output is correct
25	Correct	33 ms	43000 KB	Output is correct
26	Correct	32 ms	43064 KB	Output is correct
27	Correct	31 ms	42880 KB	Output is correct
28	Correct	32 ms	42880 KB	Output is correct
29	Correct	31 ms	42872 KB	Output is correct
30	Correct	31 ms	42880 KB	Output is correct
31	Correct	777 ms	142936 KB	Output is correct
32	Correct	109 ms	53256 KB	Output is correct
33	Correct	730 ms	136684 KB	Output is correct
34	Correct	736 ms	136912 KB	Output is correct
35	Correct	748 ms	142572 KB	Output is correct
36	Correct	757 ms	142188 KB	Output is correct
37	Correct	603 ms	127212 KB	Output is correct
38	Correct	600 ms	126948 KB	Output is correct
39	Correct	471 ms	112452 KB	Output is correct
40	Correct	505 ms	116332 KB	Output is correct
41	Correct	696 ms	123112 KB	Output is correct
42	Correct	698 ms	123872 KB	Output is correct
43	Correct	100 ms	51192 KB	Output is correct
44	Correct	701 ms	123116 KB	Output is correct
45	Correct	644 ms	114028 KB	Output is correct
46	Correct	576 ms	98372 KB	Output is correct
47	Correct	407 ms	96748 KB	Output is correct
48	Correct	381 ms	92600 KB	Output is correct
49	Correct	444 ms	103276 KB	Output is correct
50	Correct	504 ms	121176 KB	Output is correct
51	Correct	432 ms	98672 KB	Output is correct
52	Correct	2310 ms	397568 KB	Output is correct
53	Correct	2144 ms	377280 KB	Output is correct
54	Correct	2844 ms	575156 KB	Output is correct
55	Correct	2426 ms	427112 KB	Output is correct
56	Correct	2201 ms	387428 KB	Output is correct
57	Correct	2136 ms	382372 KB	Output is correct
58	Correct	2707 ms	584468 KB	Output is correct
59	Correct	2340 ms	423684 KB	Output is correct
60	Correct	2222 ms	376912 KB	Output is correct
61	Correct	2139 ms	366180 KB	Output is correct
62	Correct	1529 ms	348424 KB	Output is correct
63	Correct	1663 ms	385384 KB	Output is correct
64	Correct	3584 ms	489928 KB	Output is correct
65	Correct	419 ms	96840 KB	Output is correct
66	Correct	3525 ms	487324 KB	Output is correct
67	Correct	4212 ms	680692 KB	Output is correct
68	Correct	3666 ms	503592 KB	Output is correct
69	Correct	3804 ms	534604 KB	Output is correct
70	Correct	3880 ms	467440 KB	Output is correct
71	Correct	3871 ms	479092 KB	Output is correct
72	Correct	4214 ms	697788 KB	Output is correct
73	Correct	3613 ms	525844 KB	Output is correct
74	Correct	3580 ms	504528 KB	Output is correct
75	Correct	3475 ms	471044 KB	Output is correct
76	Correct	1973 ms	439568 KB	Output is correct
77	Correct	1956 ms	434188 KB	Output is correct
78	Correct	2227 ms	450192 KB	Output is correct
79	Correct	2508 ms	458120 KB	Output is correct
80	Correct	2428 ms	448336 KB	Output is correct
81	Correct	819 ms	170196 KB	Output is correct
82	Correct	810 ms	159316 KB	Output is correct
83	Correct	789 ms	150176 KB	Output is correct
84	Correct	681 ms	133484 KB	Output is correct
85	Correct	669 ms	137068 KB	Output is correct
86	Correct	729 ms	124504 KB	Output is correct
87	Correct	717 ms	138332 KB	Output is correct
88	Correct	776 ms	146384 KB	Output is correct
89	Correct	720 ms	127320 KB	Output is correct
90	Correct	185 ms	64496 KB	Output is correct
91	Correct	788 ms	165332 KB	Output is correct
92	Correct	801 ms	156868 KB	Output is correct
93	Correct	778 ms	153180 KB	Output is correct
94	Correct	741 ms	143784 KB	Output is correct
95	Correct	692 ms	127576 KB	Output is correct
96	Correct	239 ms	74832 KB	Output is correct
97	Execution timed out	5106 ms	773492 KB	Time limit exceeded
98	Halted	0 ms	0 KB	-