제출 #298457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
298457		arayi	Rectangles (IOI19_rect)	C++17	59 / 100	5113 ms	183952 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define MP make_pair
#define sc second
#define fr first
#define ad push_back
#define lli long long int
using namespace std;

const int N = 2525;
int n, m;
int aj[N][N], dz[N][N], nr[N][N], vr[N][N];
vector <pair<int, int> > fp[N], fp1[N];
int ajnr[N][N], ajvr[N][N], dznr[N][N], dzvr[N][N];
lli col[N][N], pat;
long long count_rectangles(vector<vector<int> > a)
{
	n = a.size(), m = a[0].size();
	for (int i = 0; i < n; i++)
	{
	    for(int j = 0; j < m; j++)
	    {
	        int i1;
	        i1 = 0;
	        while(j + i1 + 1 < m && a[i][j + i1 + 1] < a[i][j]) i1++;
	        aj[i][j] = i1;
	        i1 = 0;
	        while(j - i1 - 1 >= 0 && a[i][j - i1 - 1] < a[i][j]) i1++;
	        dz[i][j] = i1;
	        i1 = 0;
	        while(i + i1 + 1 < n && a[i + i1 + 1][j] < a[i][j]) i1++;
	        nr[i][j] = i1;
            i1 = 0;
	        while(i - i1 - 1 >= 0 && a[i - i1 - 1][j] < a[i][j]) i1++;
	        vr[i][j] = i1;
	        fp[nr[i][j]].ad(MP(i, j));
	        fp1[vr[i][j]].ad(MP(i, j));
	        ajnr[i][j] = ajvr[i][j] = m - j;
	        dznr[i][j] = dzvr[i][j] = j;
	    }
	}
	for(int l = 1; l < n - 1; l++)
    {
        for(auto p : fp[l - 1])
        {
            //if(l == 1) cout << p.fr << " " << p.sc << " " << endl;
            for(int j = p.sc; j < m; j++)
                dznr[p.fr][j] = min(dznr[p.fr][j], j - p.sc);
            for(int j = p.sc; j >= 0; j--)
                ajnr[p.fr][j] = min(ajnr[p.fr][j], p.sc - j);
        }
        for(auto p : fp1[l - 1])
        {
             for(int j = p.sc; j < m; j++)
                dzvr[p.fr][j] = min(dzvr[p.fr][j], j - p.sc);
            for(int j = p.sc; j >= 0; j--)
                ajvr[p.fr][j] = min(ajvr[p.fr][j], p.sc - j);
        }
        for (int i = n - 1; i >= l; i--)
            for(int j = 0; j < m; j++)
                if(l > 1) dz[i][j] = min(dz[i][j], dz[i - 1][j]);
        //cout << dz[4][4] << endl;
        for (int i = n - 1; i >= l; i--)
        {
            for(int j = 0; j < m - 1; j++)
            {
                if(l > 1) aj[i][j] = min(aj[i][j], aj[i - 1][j]);
                int sm = min(ajvr[i + 1][j + 1], ajnr[i - l][j + 1]);
                sm = min(sm, aj[i][j]);
                //if(l == 2) cout << sm << " ";
                for(int k = j + 2; k < min(m, j + sm + 2); k++)
                    if(k - j - 1 <= dz[i][k]) pat++;
            }
            //if(l == 2) cout << endl;
        }
        //cout << pat << endl;
    }
    return pat;
}

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