Submission #800499

#	Time	Username	Problem	Language	Result	Execution time	Memory
800499		lollipop	Rectangles (IOI19_rect)	C++17	72 / 100	1788 ms	1048576 KiB

rect

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int NN = 6e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "rect.h"
int n , m ;
vector < int > h[ 2501 ][ 2501 ] , w[ 2501 ][ 2501 ] ;
vector<vector<int> > a ;

void pot_build(){
    FOR( i , n ){
    	int clos[ 2501 ] ;	    	
    	stack < int > st ;
    	FOR( j , m ){
    		clos[ j ] = -1 ; 
	    	while( true ){
	    		if( st.size() == 0 ) break ;
	    		int x = st.top() ;	    		
	    		if( a[ i ][ x ] < a[ i ][ j ] ){
	    			clos[ x ] = j ; st.pop() ; 
				} else break ;
			}
			st.push( j ) ;
	    }
	    FOR( j , m ){
	       int lst = j + 1 ;
	       while( true ){
	       	 if( lst >= m || lst == -1 ) break ;
	       	 int nx = clos[ lst ] ;
	       	 if( a[ i ][ lst ] >= a[ i ][ j ] ) break ; 
	       	 if( nx != -1 ) w[ j ][ nx ].pb( i ) ;
	       	 lst = nx ; 
		   }
		}
	}  	
	// now for the horizontal ones 
    FOR( j , m ){
    	int clos[ 2501 ] ; stack < int > st ;
    	FOR( i , n ){
    		clos[ i ] = -1 ; 
	    	while( true ){
	    		if( st.size() == 0 ) break ;
	    		int x = st.top() ;
	    		if( a[ x ][ j ] < a[ i ][ j ] ){
	    			clos[ x ] = i ; st.pop() ; 
				} else break ;
			}
			st.push( i ) ;
	    }
	    FOR( i , n ){
	       int lst = i + 1 ;
	       while( true ){
	       	 if( lst >= n || lst == -1 ) break ;
	       	 int nx = clos[ lst ] ;
	       	 if( a[ lst ][ j ] >= a[ i ][ j ] ) break ; 
	       	 if( nx != -1 ) h[ i ][ nx ].pb( j ) ;
	       	 lst = nx ; 
		   }
		}
	}  	 
}
struct W{
	int l , r , high , low ;
};
struct H{
	int high , low , l , r ;
};
vector < W > ww[ 2501 ][ 2501 ] ;
vector < H > hh[ 2501 ][ 2501 ] ; 
void make_potential_sides(){
	 FOR( j , m ){
	 	for( int j1 = j + 1 ; j1 < m ; j1 ++ ){
	 		if( w[ j ][ j1 ].size() == 0 ) continue ;
	 		int lst = w[ j ][ j1 ][ 0 ] ;
	 		int fr = w[ j ][ j1 ][ 0 ] ;
	 		for( int ps = 1 ; ps < w[ j ][ j1 ].size() ; ps ++ ){
	 		     if( w[ j ][ j1 ][ ps ] - 1 != lst ){
	 		     	// push for future 
	 		     	W cur ; cur.l = j , cur.r = j1 , cur.high = fr , cur.low = lst ;
	 		     	for( int kk = fr ; kk <= lst ; kk ++ ) ww[ kk ][ j1 ].pb( cur ) ;
	 		     	// make for new 
	 		     	fr = w[ j ][ j1 ][ ps ] ; 
	 		     	lst = w[ j ][ j1 ][ ps ] ;
				 }
				 else lst = w[ j ][ j1 ][ ps ] ; 	
			}
	 		// push for future 
	 		W cur ; cur.l = j , cur.r = j1 , cur.high = fr , cur.low = lst ;
	 		for( int kk = fr ; kk <= lst ; kk ++ ) ww[ kk ][ j1 ].pb( cur ) ;
		 }
	 }
	 // now for horizontals 
	 FOR( i , n ){
	 	for( int i1 = i + 1 ; i1 < n ; i1 ++ ){
	 		if( h[ i ][ i1 ].size() == 0 ) continue ;
	 		int lst = h[ i ][ i1 ][ 0 ] ;
	 		int fr = h[ i ][ i1 ][ 0 ] ;
	 		for( int ps = 1 ; ps < h[ i ][ i1 ].size() ; ps ++ ){
	 		     if( h[ i ][ i1 ][ ps ] - 1 != lst ){
	 		     	// push for future 
	 		     	H cur ; cur.high = i , cur.low = i1 , cur.l = fr , cur.r = lst ;
	 		     	for( int kk = fr ; kk <= lst ; kk ++ ) hh[ i1 ][ kk ].pb( cur ) ;
	 		     	// make for new 
	 		     	fr = h[ i ][ i1 ][ ps ] ; 
	 		     	lst = h[ i ][ i1 ][ ps ] ;
				 }
				 else lst = h[ i ][ i1 ][ ps ] ; 	
			}
	 		// push for future 
	 		H cur ; cur.high = i , cur.low = i1 , cur.l = fr , cur.r = lst ;
	 	    for( int kk = fr ; kk <= lst ; kk ++ ) hh[ i1 ][ kk ].pb( cur ) ;
		 }
	 }	 
}
// sort to make the problem solvable
bool sortbyw( W a , W b ){
	 return a.high > b.high ;
}
bool sortbyh( H a , H b ){
	 return a.high > b.high ; 
}
// get the sum ==> number of intersections
int fen[ 3000 ] ;
void add( int pos , int val ){
	 pos ++ ; 
	 for( int j = pos ; j < 3000 ; j = j + ( j & ( - j ) ) ) fen[ j ] += val ;
}
int get( int l , int r ){
	l ++ , r ++ ;
	int sum = 0 ;
	for( int j = r ; j > 0 ; j = j - ( j & ( - j ) ) ) sum += fen[ j ] ;
	for( int j = l - 1 ; j > 0 ; j = j - ( j & ( - j ) ) ) sum -= fen[ j ] ;
	return sum ;	
}
long long count_rectangles(vector<vector<int> > A){
    n = A.size() , m = A[ 0 ].size() ; a = A ; 
 	pot_build() ;
  	make_potential_sides() ;
  	FOR( i , n ) FOR( j , m ){
  	   sort( ww[ i ][ j ].begin() , ww[ i ][ j ].end() , sortbyw ) ;
	   sort( hh[ i ][ j ].begin() , hh[ i ][ j ].end() , sortbyh ) ;	
	}
	// now calculate the answer
    ll ans = 0 ;
    FOR( i , n ){
    	FOR( j , m ){
    		// consider this as the low right spot 
    		if( j == 0 || i == 0 ) continue ;
    		int pos = 0 ;
    	//	cout << get( 0 , m ) << endl ;
    		for( auto x : ww[ i - 1 ][ j ] ){
    			add( x.l , 1 ) ;
			}
			for( auto x : hh[ i ][ j - 1 ] ){
				while( true ){
					if( pos == ww[ i - 1 ][ j ].size() ) break ;
					if( ww[ i - 1 ][ j ][ pos ].high <= x.high + 1 ) break ;
					add( ww[ i - 1 ][ j ][ pos ].l , -1 ) ;
					pos ++ ;
				}
				ans = ans + get( x.l - 1 , j - 2 ) ;
			}
		//	cout << i << " " << j << " " << ans << endl ;
		//	cout << ww[ i - 1 ][ j ].size() << " " << hh[ i ][ j - 1 ].size() << endl ;
			for( ; pos < ww[ i - 1 ][ j ].size() ; pos ++ ){
				add( ww[ i - 1 ][ j ][ pos ].l , -1 ) ;				
			}
		}
	}
	return ans ;
}



//  static const int buf_size = 4096;

//  inline int getChar() {
//  	static char buf[buf_size];
//  	static int len = 0, pos = 0;
//  	if (pos == len) {
//  		pos = 0;
//  		len = fread(buf, 1, buf_size, stdin);
//  	}
//  	if (pos == len)
//  		return -1;
//  	return buf[pos++];
//  }

//  inline int readChar() {
//  	int c = getChar();
//  	while (c <= 32)
//  		c = getChar();
//  	return c;
//  }

//  inline int readInt() {
//  	int s = 1, c = readChar();
//  	int x = 0;
//  	while ('0' <= c && c <= '9') {
//  		x = x * 10 + c - '0';
//  		c = getChar();
//  	}
//  	return x;
//  }

//  int main() {
//  	cin >> n ;
//       cin >> m ;
//  	vector<vector<int> > a(n, vector<int>(m));
//  	for (int i = 0; i < n; i++) {
//  		for (int j = 0; j < m; j++) {
//  		    a[i][j] = readInt();
//  		}
//  	}
//  	fclose(stdin);

//  	long long result= count_rectangles(a);

//  	printf("%lld\n", result);
//  	fclose(stdout);
//  	return 0;
//  }

Compilation message (stderr)

rect.cpp: In function 'void make_potential_sides()':
rect.cpp:103:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for( int ps = 1 ; ps < w[ j ][ j1 ].size() ; ps ++ ){
      |                       ~~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:125:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for( int ps = 1 ; ps < h[ i ][ i1 ].size() ; ps ++ ){
      |                       ~~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:183:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<W>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |      if( pos == ww[ i - 1 ][ j ].size() ) break ;
      |          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:192:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<W>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |    for( ; pos < ww[ i - 1 ][ j ].size() ; pos ++ ){
      |           ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28