답안 #295292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295292	2020-09-09T15:06:58 Z	CaroLinda	새 집 (APIO18_new_home)	C++14	80 / 100	5000 ms	758276 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 optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#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: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:602:14:   required from here
new_home.cpp:561:9: warning: comparison of constant '0' with boolean expression is always false [-Wbool-compare]
  561 |   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

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	28544 KB	Output is correct
2	Correct	26 ms	28544 KB	Output is correct
3	Correct	26 ms	28584 KB	Output is correct
4	Correct	20 ms	28544 KB	Output is correct
5	Correct	23 ms	28700 KB	Output is correct
6	Correct	24 ms	28928 KB	Output is correct
7	Correct	33 ms	29048 KB	Output is correct
8	Correct	24 ms	28968 KB	Output is correct
9	Correct	24 ms	28976 KB	Output is correct
10	Correct	22 ms	28940 KB	Output is correct
11	Correct	26 ms	28860 KB	Output is correct
12	Correct	27 ms	28768 KB	Output is correct
13	Correct	23 ms	28800 KB	Output is correct
14	Correct	22 ms	28808 KB	Output is correct
15	Correct	23 ms	28928 KB	Output is correct
16	Correct	22 ms	28960 KB	Output is correct
17	Correct	24 ms	28928 KB	Output is correct
18	Correct	23 ms	28928 KB	Output is correct
19	Correct	23 ms	28928 KB	Output is correct
20	Correct	24 ms	28920 KB	Output is correct
21	Correct	24 ms	28672 KB	Output is correct
22	Correct	24 ms	29092 KB	Output is correct
23	Correct	30 ms	29056 KB	Output is correct
24	Correct	24 ms	28952 KB	Output is correct
25	Correct	22 ms	28968 KB	Output is correct
26	Correct	24 ms	28800 KB	Output is correct
27	Correct	23 ms	28800 KB	Output is correct
28	Correct	28 ms	28792 KB	Output is correct
29	Correct	23 ms	28792 KB	Output is correct
30	Correct	22 ms	28792 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	28544 KB	Output is correct
2	Correct	26 ms	28544 KB	Output is correct
3	Correct	26 ms	28584 KB	Output is correct
4	Correct	20 ms	28544 KB	Output is correct
5	Correct	23 ms	28700 KB	Output is correct
6	Correct	24 ms	28928 KB	Output is correct
7	Correct	33 ms	29048 KB	Output is correct
8	Correct	24 ms	28968 KB	Output is correct
9	Correct	24 ms	28976 KB	Output is correct
10	Correct	22 ms	28940 KB	Output is correct
11	Correct	26 ms	28860 KB	Output is correct
12	Correct	27 ms	28768 KB	Output is correct
13	Correct	23 ms	28800 KB	Output is correct
14	Correct	22 ms	28808 KB	Output is correct
15	Correct	23 ms	28928 KB	Output is correct
16	Correct	22 ms	28960 KB	Output is correct
17	Correct	24 ms	28928 KB	Output is correct
18	Correct	23 ms	28928 KB	Output is correct
19	Correct	23 ms	28928 KB	Output is correct
20	Correct	24 ms	28920 KB	Output is correct
21	Correct	24 ms	28672 KB	Output is correct
22	Correct	24 ms	29092 KB	Output is correct
23	Correct	30 ms	29056 KB	Output is correct
24	Correct	24 ms	28952 KB	Output is correct
25	Correct	22 ms	28968 KB	Output is correct
26	Correct	24 ms	28800 KB	Output is correct
27	Correct	23 ms	28800 KB	Output is correct
28	Correct	28 ms	28792 KB	Output is correct
29	Correct	23 ms	28792 KB	Output is correct
30	Correct	22 ms	28792 KB	Output is correct
31	Correct	813 ms	128540 KB	Output is correct
32	Correct	96 ms	38920 KB	Output is correct
33	Correct	795 ms	122312 KB	Output is correct
34	Correct	791 ms	122536 KB	Output is correct
35	Correct	789 ms	128044 KB	Output is correct
36	Correct	795 ms	127832 KB	Output is correct
37	Correct	631 ms	112668 KB	Output is correct
38	Correct	635 ms	112708 KB	Output is correct
39	Correct	477 ms	98116 KB	Output is correct
40	Correct	524 ms	102216 KB	Output is correct
41	Correct	681 ms	108764 KB	Output is correct
42	Correct	707 ms	109476 KB	Output is correct
43	Correct	90 ms	37112 KB	Output is correct
44	Correct	735 ms	108840 KB	Output is correct
45	Correct	647 ms	99668 KB	Output is correct
46	Correct	555 ms	84172 KB	Output is correct
47	Correct	380 ms	82540 KB	Output is correct
48	Correct	363 ms	78392 KB	Output is correct
49	Correct	418 ms	88940 KB	Output is correct
50	Correct	487 ms	106972 KB	Output is correct
51	Correct	436 ms	84464 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2279 ms	382656 KB	Output is correct
2	Correct	2080 ms	362676 KB	Output is correct
3	Correct	2914 ms	561760 KB	Output is correct
4	Correct	2405 ms	414060 KB	Output is correct
5	Correct	2157 ms	374384 KB	Output is correct
6	Correct	2080 ms	369312 KB	Output is correct
7	Correct	2610 ms	571432 KB	Output is correct
8	Correct	2355 ms	410536 KB	Output is correct
9	Correct	2159 ms	363604 KB	Output is correct
10	Correct	2043 ms	351936 KB	Output is correct
11	Correct	1470 ms	332336 KB	Output is correct
12	Correct	1588 ms	369608 KB	Output is correct

Subtask #4

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3481 ms	473132 KB	Output is correct
2	Correct	382 ms	79432 KB	Output is correct
3	Correct	3571 ms	471684 KB	Output is correct
4	Correct	4083 ms	663860 KB	Output is correct
5	Correct	3564 ms	487412 KB	Output is correct
6	Correct	3653 ms	518656 KB	Output is correct
7	Correct	3634 ms	451512 KB	Output is correct
8	Correct	3535 ms	463128 KB	Output is correct
9	Correct	3772 ms	681520 KB	Output is correct
10	Correct	3436 ms	509700 KB	Output is correct
11	Correct	3552 ms	488348 KB	Output is correct
12	Correct	3508 ms	454532 KB	Output is correct
13	Correct	2025 ms	423564 KB	Output is correct
14	Correct	2037 ms	417416 KB	Output is correct
15	Correct	2264 ms	433300 KB	Output is correct
16	Correct	2517 ms	441128 KB	Output is correct
17	Correct	2405 ms	431368 KB	Output is correct

Subtask #5

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	28544 KB	Output is correct
2	Correct	26 ms	28544 KB	Output is correct
3	Correct	26 ms	28584 KB	Output is correct
4	Correct	20 ms	28544 KB	Output is correct
5	Correct	23 ms	28700 KB	Output is correct
6	Correct	24 ms	28928 KB	Output is correct
7	Correct	33 ms	29048 KB	Output is correct
8	Correct	24 ms	28968 KB	Output is correct
9	Correct	24 ms	28976 KB	Output is correct
10	Correct	22 ms	28940 KB	Output is correct
11	Correct	26 ms	28860 KB	Output is correct
12	Correct	27 ms	28768 KB	Output is correct
13	Correct	23 ms	28800 KB	Output is correct
14	Correct	22 ms	28808 KB	Output is correct
15	Correct	23 ms	28928 KB	Output is correct
16	Correct	22 ms	28960 KB	Output is correct
17	Correct	24 ms	28928 KB	Output is correct
18	Correct	23 ms	28928 KB	Output is correct
19	Correct	23 ms	28928 KB	Output is correct
20	Correct	24 ms	28920 KB	Output is correct
21	Correct	24 ms	28672 KB	Output is correct
22	Correct	24 ms	29092 KB	Output is correct
23	Correct	30 ms	29056 KB	Output is correct
24	Correct	24 ms	28952 KB	Output is correct
25	Correct	22 ms	28968 KB	Output is correct
26	Correct	24 ms	28800 KB	Output is correct
27	Correct	23 ms	28800 KB	Output is correct
28	Correct	28 ms	28792 KB	Output is correct
29	Correct	23 ms	28792 KB	Output is correct
30	Correct	22 ms	28792 KB	Output is correct
31	Correct	813 ms	128540 KB	Output is correct
32	Correct	96 ms	38920 KB	Output is correct
33	Correct	795 ms	122312 KB	Output is correct
34	Correct	791 ms	122536 KB	Output is correct
35	Correct	789 ms	128044 KB	Output is correct
36	Correct	795 ms	127832 KB	Output is correct
37	Correct	631 ms	112668 KB	Output is correct
38	Correct	635 ms	112708 KB	Output is correct
39	Correct	477 ms	98116 KB	Output is correct
40	Correct	524 ms	102216 KB	Output is correct
41	Correct	681 ms	108764 KB	Output is correct
42	Correct	707 ms	109476 KB	Output is correct
43	Correct	90 ms	37112 KB	Output is correct
44	Correct	735 ms	108840 KB	Output is correct
45	Correct	647 ms	99668 KB	Output is correct
46	Correct	555 ms	84172 KB	Output is correct
47	Correct	380 ms	82540 KB	Output is correct
48	Correct	363 ms	78392 KB	Output is correct
49	Correct	418 ms	88940 KB	Output is correct
50	Correct	487 ms	106972 KB	Output is correct
51	Correct	436 ms	84464 KB	Output is correct
52	Correct	787 ms	154324 KB	Output is correct
53	Correct	780 ms	143444 KB	Output is correct
54	Correct	744 ms	134380 KB	Output is correct
55	Correct	639 ms	117612 KB	Output is correct
56	Correct	640 ms	121448 KB	Output is correct
57	Correct	646 ms	108760 KB	Output is correct
58	Correct	685 ms	122716 KB	Output is correct
59	Correct	690 ms	130652 KB	Output is correct
60	Correct	661 ms	111708 KB	Output is correct
61	Correct	169 ms	48876 KB	Output is correct
62	Correct	735 ms	149720 KB	Output is correct
63	Correct	740 ms	141280 KB	Output is correct
64	Correct	752 ms	137700 KB	Output is correct
65	Correct	705 ms	128096 KB	Output is correct
66	Correct	676 ms	112092 KB	Output is correct
67	Correct	221 ms	59600 KB	Output is correct

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	28544 KB	Output is correct
2	Correct	26 ms	28544 KB	Output is correct
3	Correct	26 ms	28584 KB	Output is correct
4	Correct	20 ms	28544 KB	Output is correct
5	Correct	23 ms	28700 KB	Output is correct
6	Correct	24 ms	28928 KB	Output is correct
7	Correct	33 ms	29048 KB	Output is correct
8	Correct	24 ms	28968 KB	Output is correct
9	Correct	24 ms	28976 KB	Output is correct
10	Correct	22 ms	28940 KB	Output is correct
11	Correct	26 ms	28860 KB	Output is correct
12	Correct	27 ms	28768 KB	Output is correct
13	Correct	23 ms	28800 KB	Output is correct
14	Correct	22 ms	28808 KB	Output is correct
15	Correct	23 ms	28928 KB	Output is correct
16	Correct	22 ms	28960 KB	Output is correct
17	Correct	24 ms	28928 KB	Output is correct
18	Correct	23 ms	28928 KB	Output is correct
19	Correct	23 ms	28928 KB	Output is correct
20	Correct	24 ms	28920 KB	Output is correct
21	Correct	24 ms	28672 KB	Output is correct
22	Correct	24 ms	29092 KB	Output is correct
23	Correct	30 ms	29056 KB	Output is correct
24	Correct	24 ms	28952 KB	Output is correct
25	Correct	22 ms	28968 KB	Output is correct
26	Correct	24 ms	28800 KB	Output is correct
27	Correct	23 ms	28800 KB	Output is correct
28	Correct	28 ms	28792 KB	Output is correct
29	Correct	23 ms	28792 KB	Output is correct
30	Correct	22 ms	28792 KB	Output is correct
31	Correct	813 ms	128540 KB	Output is correct
32	Correct	96 ms	38920 KB	Output is correct
33	Correct	795 ms	122312 KB	Output is correct
34	Correct	791 ms	122536 KB	Output is correct
35	Correct	789 ms	128044 KB	Output is correct
36	Correct	795 ms	127832 KB	Output is correct
37	Correct	631 ms	112668 KB	Output is correct
38	Correct	635 ms	112708 KB	Output is correct
39	Correct	477 ms	98116 KB	Output is correct
40	Correct	524 ms	102216 KB	Output is correct
41	Correct	681 ms	108764 KB	Output is correct
42	Correct	707 ms	109476 KB	Output is correct
43	Correct	90 ms	37112 KB	Output is correct
44	Correct	735 ms	108840 KB	Output is correct
45	Correct	647 ms	99668 KB	Output is correct
46	Correct	555 ms	84172 KB	Output is correct
47	Correct	380 ms	82540 KB	Output is correct
48	Correct	363 ms	78392 KB	Output is correct
49	Correct	418 ms	88940 KB	Output is correct
50	Correct	487 ms	106972 KB	Output is correct
51	Correct	436 ms	84464 KB	Output is correct
52	Correct	2279 ms	382656 KB	Output is correct
53	Correct	2080 ms	362676 KB	Output is correct
54	Correct	2914 ms	561760 KB	Output is correct
55	Correct	2405 ms	414060 KB	Output is correct
56	Correct	2157 ms	374384 KB	Output is correct
57	Correct	2080 ms	369312 KB	Output is correct
58	Correct	2610 ms	571432 KB	Output is correct
59	Correct	2355 ms	410536 KB	Output is correct
60	Correct	2159 ms	363604 KB	Output is correct
61	Correct	2043 ms	351936 KB	Output is correct
62	Correct	1470 ms	332336 KB	Output is correct
63	Correct	1588 ms	369608 KB	Output is correct
64	Correct	3481 ms	473132 KB	Output is correct
65	Correct	382 ms	79432 KB	Output is correct
66	Correct	3571 ms	471684 KB	Output is correct
67	Correct	4083 ms	663860 KB	Output is correct
68	Correct	3564 ms	487412 KB	Output is correct
69	Correct	3653 ms	518656 KB	Output is correct
70	Correct	3634 ms	451512 KB	Output is correct
71	Correct	3535 ms	463128 KB	Output is correct
72	Correct	3772 ms	681520 KB	Output is correct
73	Correct	3436 ms	509700 KB	Output is correct
74	Correct	3552 ms	488348 KB	Output is correct
75	Correct	3508 ms	454532 KB	Output is correct
76	Correct	2025 ms	423564 KB	Output is correct
77	Correct	2037 ms	417416 KB	Output is correct
78	Correct	2264 ms	433300 KB	Output is correct
79	Correct	2517 ms	441128 KB	Output is correct
80	Correct	2405 ms	431368 KB	Output is correct
81	Correct	787 ms	154324 KB	Output is correct
82	Correct	780 ms	143444 KB	Output is correct
83	Correct	744 ms	134380 KB	Output is correct
84	Correct	639 ms	117612 KB	Output is correct
85	Correct	640 ms	121448 KB	Output is correct
86	Correct	646 ms	108760 KB	Output is correct
87	Correct	685 ms	122716 KB	Output is correct
88	Correct	690 ms	130652 KB	Output is correct
89	Correct	661 ms	111708 KB	Output is correct
90	Correct	169 ms	48876 KB	Output is correct
91	Correct	735 ms	149720 KB	Output is correct
92	Correct	740 ms	141280 KB	Output is correct
93	Correct	752 ms	137700 KB	Output is correct
94	Correct	705 ms	128096 KB	Output is correct
95	Correct	676 ms	112092 KB	Output is correct
96	Correct	221 ms	59600 KB	Output is correct
97	Execution timed out	5010 ms	758276 KB	Time limit exceeded
98	Halted	0 ms	0 KB	-