oj.uz

Submission #51617

# Submission time Handle Problem Language Result Execution time Memory
51617 2018-06-19T08:18:54 Z model_code Pairs (IOI07_pairs) C++17
100 / 100
 298 ms 41592 KB 
#include <algorithm>
#include <cstdio>

typedef long long llint;

using namespace std;

struct loga3d {
   int a[225*225*225];
   int X, Y, Z;

   inline int & polje( int x, int y, int z ) {
      return a[ ((x-1)*Y + (y-1))*Z + (z-1) ];
   }

   int query( int x0, int y0, int z0 ) {
      int ret = 0;
      for( int x = x0; x > 0; x -= x&-x )
         for( int y = y0; y > 0; y -= y&-y )
            for( int z = z0; z > 0; z -= z&-z )
               ret += polje( x, y, z );
      return ret;
   }

   int query( int x1, int x2, int y1, int y2, int z1, int z2 ) {
      --x1; 
      --y1; 
      --z1;
      if(x1 < 0) x1 = 0; if(x2 > X) x2 = X;
      if(y1 < 0) y1 = 0; if(y2 > Y) y2 = Y;
      if(z1 < 0) z1 = 0; if(z2 > Z) z2 = Z;

      return query( x2, y2, z2 ) 
         - query( x1, y2, z2 ) - query( x2, y1, z2 ) - query( x2, y2, z1 )
         + query( x1, y1, z2 ) + query( x1, y2, z1 ) + query( x2, y1, z1 )
         - query( x1, y1, z1 );
   }

   void update( int x0, int y0, int z0, int val ) {
      for( int x = x0; x <= X; x += x&-x )
         for( int y = y0; y <= Y; y += y&-y )
            for( int z = z0; z <= Z; z += z&-z )
               polje( x, y, z ) += val;
   }
};

loga3d L;
int B, N, K, M;

struct point {
   int x, y, z;
   int a, b, c, d;
} tocke[100000];

bool operator < ( const point &P, const point &Q ) { return P.a < Q.a; }
 
int main( void ) {
   scanf( "%d%d%d%d", &B, &N, &K, &M );

   if( B == 1 ) { L.X = 1;   L.Y = 1;   L.Z = 1;   }
   if( B == 2 ) { L.X = 2*M; L.Y = 1;   L.Z = 1;   }
   if( B == 3 ) { L.X = 3*M; L.Y = 3*M; L.Z = 3*M; }

   for( int i = 0; i < N; ++i ) {
      point T;
      if( B == 1 ) {
         scanf( "%d", &T.x ); 
         T.a = T.x; 
         T.b = 1;  
         T.c = 1; 
         T.d = 1;
      }
      if( B == 2 ) {
         scanf( "%d%d", &T.x, &T.y ); 
         T.a = T.x+T.y - 1;
         T.b = T.x-T.y + M;
         T.c = 1; 
         T.d = 1;
      }
      if( B == 3 ) {
         scanf( "%d%d%d", &T.x, &T.y, &T.z );
         T.a = T.x+T.y+T.z - 2;
         T.b = T.x+T.y-T.z + M-1;
         T.c = T.x-T.y+T.z + M-1;
         T.d = T.x-T.y-T.z + M+M;
      }
      tocke[i] = T;
   }
   sort( tocke, tocke+N ); 

   llint ret = 0;
   int head = 0, tail = 0;
   while( head < N ) {
      while( tocke[head].a - tocke[tail].a > K ) 
         L.update( tocke[tail].b, tocke[tail].c, tocke[tail].d, -1 ), ++tail;

      ret += L.query(  tocke[head].b-K, tocke[head].b+K,
                       tocke[head].c-K, tocke[head].c+K,
                       tocke[head].d-K, tocke[head].d+K );

      L.update( tocke[head].b, tocke[head].c, tocke[head].d, 1 ), ++head;
   }

   printf( "%lld\n", ret );

   return 0;
}

Compilation message

pairs.cpp: In member function 'int loga3d::query(int, int, int, int, int, int)':
pairs.cpp:29:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
       if(x1 < 0) x1 = 0; if(x2 > X) x2 = X;
       ^~
pairs.cpp:29:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
       if(x1 < 0) x1 = 0; if(x2 > X) x2 = X;
                          ^~
pairs.cpp:30:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
       if(y1 < 0) y1 = 0; if(y2 > Y) y2 = Y;
       ^~
pairs.cpp:30:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
       if(y1 < 0) y1 = 0; if(y2 > Y) y2 = Y;
                          ^~
pairs.cpp:31:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
       if(z1 < 0) z1 = 0; if(z2 > Z) z2 = Z;
       ^~
pairs.cpp:31:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
       if(z1 < 0) z1 = 0; if(z2 > Z) z2 = Z;
                          ^~
pairs.cpp: In function 'int main()':
pairs.cpp:58:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf( "%d%d%d%d", &B, &N, &K, &M );
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:67:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf( "%d", &T.x ); 
          ~~~~~^~~~~~~~~~~~~~
pairs.cpp:74:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf( "%d%d", &T.x, &T.y ); 
          ~~~~~^~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:81:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf( "%d%d%d", &T.x, &T.y, &T.z );
          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3244 KB Output is correct
2 Correct 25 ms 3244 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3244 KB Output is correct
2 Correct 31 ms 3244 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3280 KB Output is correct
2 Correct 31 ms 3280 KB Output is correct
3 Correct 34 ms 3280 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3280 KB Output is correct
2 Correct 3 ms 3280 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3916 KB Output is correct
2 Correct 34 ms 4504 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5396 KB Output is correct
2 Correct 47 ms 5972 KB Output is correct
3 Correct 47 ms 6864 KB Output is correct
4 Correct 48 ms 7736 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 9340 KB Output is correct
2 Correct 68 ms 10488 KB Output is correct
3 Correct 56 ms 11580 KB Output is correct
4 Correct 55 ms 12656 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 20992 KB Output is correct
2 Correct 10 ms 20992 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 20992 KB Output is correct
2 Correct 61 ms 20992 KB Output is correct
3 Correct 57 ms 20992 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 26772 KB Output is correct
2 Correct 196 ms 27656 KB Output is correct
3 Correct 92 ms 28528 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 39824 KB Output is correct
2 Correct 232 ms 40620 KB Output is correct
3 Correct 109 ms 41592 KB Output is correct