Submission #794241

#	Time	Username	Problem	Language	Result	Execution time	Memory
794241		lollipop	Rectangles (IOI19_rect)	C++17	0 / 100	8 ms	596 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"

short int clos[ 201 ][ 201 ][ 201 ] ;
int mx[ 701 ] , cnt[ 701 ] ;
long long count_rectangles(vector<vector<int> > a){
  // I hope memory limit and time limit does not kill my beautiful n^3 solution
  // I am wirting many comments coz I don't want to fuck this up
  // it slows me down and gives me time to think and check

     int n = a.size() ; 
     int m = a[ 0 ].size() ;    
     if( n < 3 || m < 3 ) return 0 ; 
     FOR( i , n - 2 ){
       // starting line number i 
       FOR( j , m ) mx[ j ] = a[ i + 1 ][ j ] ;
       for( int j = i + 2 ; j < n ; j ++ ){
         // finish line number j 
         int cl = m ;
         for( int k = m - 1 ; k >= 0 ; k -- ){
          // a column for which we are checking
            int mn = min( a[ i ][ k ] , a[ j ][ k ] ) ;
            if( mn <= mx[ k ] ) cl = k ;
            clos[ i ][ j ][ k ] = cl ;
            mx[ k ] = max( mx[ k ] , a[ j ][ k ] ) ;
         }
       }
     } 
     // now shitty calculations, excuse my language 
     // if I get this right on first try I will continue using comments in future
     ll ans = 0 ;
     FOR( i , n - 2 ){
      FOR( j , m - 2 ){
        // we are at position i;j, the left start of the boarder
        // find good positions to the right and calulcate the number of them till index l
        for( int l = j ; l < m ; l ++ ) cnt[ l ] = 0 ; 
        int mx = a[ i + 1 ][ j + 1 ] ; 
        for( int l = j + 2 ; l < m ; l ++ ){
            cnt[ l ] = cnt[ l - 1 ] ; 
            int mn = min( a[ i + 1 ][ j ] , a[ i + 1 ][ l ] ) ;
            if( mn > mx ) cnt[ l ] ++ ;
            mx = max( mx , a[ i + 1 ][ l ] ) ;  
        }
        // now for the rows, but this time we calculate the answer too
        mx = a[ i + 1 ][ j + 1 ] ;
        for( int l = i + 2 ; l < n ; l ++ ){
          int mn = min( a[ i ][ j + 1 ] , a[ l ][ j + 1 ] ) ;
          if( mn > mx ){
            int cl = clos[ i ][ l ][ j + 1 ] ;
            if( cl != -1 )
            ans = ans + cnt[ cl ] ;
          }
          mx = max( mx , a[ l ][ j + 1 ] ) ;
        }

      }
     }
     // Lets hope this works :)
     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() {
// 	int n = readInt();
// 	int m = readInt();
// 	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;
// }

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