이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
// }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |