Submission #294130

#	Time	Username	Problem	Language	Result	Execution time	Memory
294130		humbertoyusta	Rectangles (IOI19_rect)	C++14	10 / 100	5102 ms	63608 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define maxn 2505
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define ll long long

ll ans;
int valid[maxn][maxn], valend[maxn][maxn];
bool valbgn[maxn][maxn];
int n, m, A[maxn][maxn];

ll f(int x){
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            valid[i][j] = valend[i][j] = valbgn[i][j] = 0;
    for(int i=1; i<n-1; i++){
        int mx = A[i][x];
        valend[i][x-1] = 1;
        valbgn[i][x-1] = 1;
        for(int j=x; j<m-1; j++){
            if( A[i][j] > mx ) mx = A[i][j];
            valid[i][j] = ( mx < A[i][x-1] && mx < A[i][j+1] );
            valend[i][j] = ( ( ( valend[i][j-1] - valend[i-1][j-1] + ( j - 1 < x ) ) != 0 ) && A[i][j] < A[i-1][j] );
            valbgn[i][j] = ( valbgn[i][j-1] && A[i][j] < A[i+1][j] );

            if( valid[i][j] ) valid[i][j] += valid[i-1][j];
            valend[i][j] += valend[i-1][j];
        }
    }
    ll res = 0;
    for(int j=x; j<m-1; j++){
        for(int i=1; i<n-1; i++){
            if( valbgn[i][j] ){
                int k = i - valid[i][j];
                res += valend[i][j] - valend[k][j];
                //if( valend[i][j] - valend[k][j] ){
                //    db(x)db(j)
                //    db(i)db(k)
                //    db(valend[i][j] - valend[k][j])
                //}
            }
        }
    }
    return res;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	n = a.size();
	m = a[0].size();
	for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            A[i][j] = a[i][j];
	for(int i=1; i<m-1; i++){
        ans += f(i);
	}
	return ans;
}

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