Submission #451915

#	Time	Username	Problem	Language	Result	Execution time	Memory
451915		ComPhyPark	Rectangles (IOI19_rect)	C++14	100 / 100	4166 ms	677656 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define SZ 2501
using namespace std;
struct rect
{
    int x1, x2, y1, y2;
};
int r[SZ][SZ], l[SZ][SZ], u[SZ][SZ], d[SZ][SZ];
int N, M;
stack<pair<int, int> > st;
vector<int> row[SZ][SZ], col[SZ][SZ];
vector<rect> ret;
bool comp(rect a, rect b)
{
    if (a.x1==b.x1 && a.x2==b.x2 && a.y1==b.y1) return a.y2<b.y2;
    if (a.x1==b.x1 && a.x2==b.x2) return a.y1<b.y1;
    if (a.x1==b.x1) return a.x2<b.x2;
    return a.x1<b.x1;
}
long long count_rectangles(vector<vector<int> > a)
{
	N=a.size(), M=a[0].size();
	long long ans=0;
    int idx1, idx2, X1, X2, Y1, Y2;
	for (int i=0; i<N; i++) {
        st.push({0, a[i][0]});
        for (int j=1; j<M; j++) {
            while (!st.empty()) {
                if (a[i][j]>=st.top().second) st.pop();
                else break;
            }
            if (st.empty()) l[i][j]=-1;
            else l[i][j]=st.top().first;
            st.push({j, a[i][j]});
        }
        while (!st.empty()) st.pop();
        st.push({M-1, a[i][M-1]});
        for (int j=M-2; j>=0; j--) {
            while (!st.empty()) {
                if (a[i][j]>=st.top().second) st.pop();
                else break;
            }
            if (st.empty()) r[i][j]=-1;
            else r[i][j]=st.top().first;
            st.push({j, a[i][j]});
        }
        while (!st.empty()) st.pop();
	}
	for (int i=0; i<M; i++) {
        while (!st.empty()) st.pop();
        st.push({0, a[0][i]});
        for (int j=1; j<N; j++) {
            while (!st.empty()) {
                if (a[j][i]>=st.top().second) st.pop();
                else break;
            }
            if (st.empty()) u[j][i]=-1;
            else u[j][i]=st.top().first;
            st.push({j, a[j][i]});
        }
        while (!st.empty()) st.pop();
        st.push({N-1, a[N-1][i]});
        for (int j=N-2; j>=0; j--) {
            while (!st.empty()) {
                if (a[j][i]>=st.top().second) st.pop();
                else break;
            }
            if (st.empty()) d[j][i]=-1;
            else d[j][i]=st.top().first;
            st.push({j, a[j][i]});
        }
	}

	for (int i=1; i<N-1; i++) for (int j=1; j<M-1; j++) if (r[i][j]!=-1 && l[i][j]!=-1) {
        Y1=l[i][j]+1, Y2=r[i][j]-1;
        if (!(!row[Y1][Y2].empty() && row[Y1][Y2][row[Y1][Y2].size()-1]==i)) row[Y1][Y2].push_back(i);
	}
	for (int j=1; j<M-1; j++) for (int i=1; i<N-1; i++) if (u[i][j]!=-1 && d[i][j]!=-1) {
	    X1=u[i][j]+1, X2=d[i][j]-1;
        if (!(!col[X1][X2].empty() && col[X1][X2][col[X1][X2].size()-1]==j)) col[X1][X2].push_back(j);
	}

	for (int i=1; i<N-1; i++) for (int j=1; j<M-1; j++) if (r[i][j]!=-1 && l[i][j]!=-1 && u[i][j]!=-1 && d[i][j]!=-1) {
        X1=u[i][j]+1, X2=d[i][j]-1, Y1=l[i][j]+1, Y2=r[i][j]-1;
        idx1=lower_bound(row[Y1][Y2].begin(), row[Y1][Y2].end(), X1)-row[Y1][Y2].begin();
        idx2=lower_bound(col[X1][X2].begin(), col[X1][X2].end(), Y1)-col[X1][X2].begin();

        if (row[Y1][Y2][idx1]==X1 && col[X1][X2][idx2]==Y1) {
            if ((idx1+X2-X1<=row[Y1][Y2].size() && row[Y1][Y2][idx1+X2-X1]==X2) && (idx2+Y2-Y1<=col[X1][X2].size() && col[X1][X2][idx2+Y2-Y1]==Y2)) {
                rect temp;
                temp.x1=X1, temp.x2=X2, temp.y1=Y1, temp.y2=Y2;
                ret.push_back(temp);
            }
        }
	}

	X1=X2=Y1=Y2=-1;
	sort(ret.begin(), ret.end(), comp);
	for (auto i : ret) {
        if (X1==i.x1 && X2==i.x2 && Y1==i.y1 && Y2==i.y2) continue;
        else {
            X1=i.x1, X2=i.x2, Y1=i.y1, Y2=i.y2;
            //printf("%d %d %d %d\n", X1, X2, Y1, Y2);
            ans++;
        }
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:90:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             if ((idx1+X2-X1<=row[Y1][Y2].size() && row[Y1][Y2][idx1+X2-X1]==X2) && (idx2+Y2-Y1<=col[X1][X2].size() && col[X1][X2][idx2+Y2-Y1]==Y2)) {
      |                  ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:90:95: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             if ((idx1+X2-X1<=row[Y1][Y2].size() && row[Y1][Y2][idx1+X2-X1]==X2) && (idx2+Y2-Y1<=col[X1][X2].size() && col[X1][X2][idx2+Y2-Y1]==Y2)) {
      |                                                                                     ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

• 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: 28 / 28