oj.uz

Submission #51615

# Submission time Handle Problem Language Result Execution time Memory
51615 2018-06-19T08:17:57 Z model_code Sails (IOI07_sails) C++17
100 / 100
 176 ms 3856 KB 
#include <algorithm>
#include <cstdio>
#include <cstring>

#define MAXN 100000
#define MAXH 100000
#define CEIL_LOG_MAXH 17

using namespace std;

struct jedro { int h, x; } a[MAXN];
bool operator < ( const jedro &A, const jedro &B ) { return A.h < B.h; }

int delta[MAXH+1];

namespace tournament {   
   int first[2<<CEIL_LOG_MAXH];
   int last[2<<CEIL_LOG_MAXH];

   int First( int a, int b, int i = 1, int lo = 0, int hi = MAXH+1 ) {
      if( lo >= b || hi <= a ) return -1;
      if( lo >= a && hi <= b ) return first[i];
      
      int mid = (lo+hi)/2;
      int L = First( a, b, 2*i, lo, mid );
      int R = First( a, b, 2*i+1, mid, hi );
      return L != -1 ? L : R;
   }

   int Last( int a, int b, int i = 1, int lo = 0, int hi = MAXH+1 ) {
      if( lo >= b || hi <= a ) return -1;
      if( lo >= a && hi <= b ) return last[i];
      
      int mid = (lo+hi)/2;
      int L = Last( a, b, 2*i, lo, mid );
      int R = Last( a, b, 2*i+1, mid, hi );
      return R != -1 ? R : L;
   }
   
   void Update( int x, int val, int i = 1, int lo = 0, int hi = MAXH+1 ) {
      if( lo > x || hi <= x ) return;
      if( lo+1 == hi ) {
         delta[x] += val;
         if( delta[x] ) first[i] = last[i] = x;
         else first[i] = last[i] = -1;
      } else {
         int mid = (lo+hi)/2;
         Update( x, val, 2*i, lo, mid );
         Update( x, val, 2*i+1, mid, hi );
         first[i] = first[2*i] != -1 ? first[2*i] : first[2*i+1];
         last[i] = last[2*i+1] != -1 ? last[2*i+1] : last[2*i];
      }
   }

   void Init() {
      memset( first, -1, sizeof first );
      memset( last, -1, sizeof last );
      Update( 0, MAXH+1 );
   }
};

int main( void ) {
   int n;
   scanf( "%d", &n );
   for( int i = 0; i < n; ++i ) scanf( "%d%d", &a[i].h, &a[i].x );
   sort( a, a+n );

   tournament::Init();
   for( int i = 0; i < n; ++i ) {
      int h0 = a[i].h - a[i].x;
      int h_up = tournament::First( h0, MAXH+1 );
      int h_down = tournament::Last( 0, h0+1 );
      if( h_up == -1 ) h_up = a[i].h;

      tournament::Update( a[i].h, 1 );
      tournament::Update( h_up, -1 );
      tournament::Update( h_down + h_up - h0, 1 );
      tournament::Update( h_down, -1 );
   }
   
   long long ret = 0, val = 0;
   for( int h = MAXH; h > 0; --h ) {
      val += delta[h];
      ret += val * (val-1)/2;
   }

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

   return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:64:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf( "%d", &n );
    ~~~~~^~~~~~~~~~~~
sails.cpp:65:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    for( int i = 0; i < n; ++i ) scanf( "%d%d", &a[i].h, &a[i].x );
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2528 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2572 KB Output is correct
2 Correct 5 ms 2956 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2956 KB Output is correct
2 Correct 47 ms 2956 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2956 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 3172 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 3616 KB Output is correct
2 Correct 120 ms 3724 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 3724 KB Output is correct
2 Correct 113 ms 3808 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 3856 KB Output is correct
2 Correct 128 ms 3856 KB Output is correct