제출 #451958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
451958		vector	Rectangles (IOI19_rect)	C++17	10 / 100	4140 ms	213592 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define SZ 2501
using namespace std;
int r[SZ][SZ], l[SZ][SZ], u[SZ][SZ], d[SZ][SZ];
int N, M;
struct rect
{
    int x1, x2, y1, y2;
};
vector<pair<pair<int, int>, int> > row, col;
set<pair<pair<int, int>, int> > vis1, vis2;
set<pair<int, int> > ans_vis;
stack<pair<int, int> > st;
bool comp(pair<pair<int, int>, int>  X, pair<pair<int, int>, int>  Y)
{
    if (X.first==Y.first) return X.second<Y.second;
    if (X.first.first==Y.first.first) return X.first.second<Y.second;
    return X.first.first<Y.first.first;
}
bool comp1(rect X, rect Y)
{
    if (X.y1==Y.y1 && X.y2==Y.y2) return X.x1<Y.x1;
    if (X.y1==Y.y1) return X.y2<Y.y2;
    return X.y1<Y.y1;
}
bool comp2(rect X, rect Y)
{
    if (X.x1==Y.x1 && X.x2==Y.x2) return X.y1<Y.y1;
    if (X.x1==Y.x1) return X.x2<Y.x2;
    return X.x1<Y.x1;
}
bool com1(rect X, int A, int B, int C)
{
    if (X.y1==A && X.y2==B) return X.x1<=C;
    if (X.y1==A) return X.y2<B;
    return X.y1<A;
}
bool com2(rect X, int A, int B, int C)
{
    if (X.x1==A && X.x2==B) return X.y1<=C;
    if (X.x1==A) return X.x2<B;
    return X.x1<A;
}
long long count_rectangles(vector<vector<int> > a)
{
	N=a.size(), M=a[0].size();
	int idx, z;
	long long ans=0;
	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) {
        pair<pair<int, int>, int> tr;
        tr.first.first=l[i][j]+1, tr.first.second=r[i][j]-1, tr.second=i;
        if (vis1.find(tr)==vis1.end()) {
            row.push_back(tr);
            vis1.insert(tr);
        }
	}
	for (int i=1; i<M-1; i++) for (int j=1; j<N-1; j++) if (u[j][i]!=-1 && d[j][i]!=-1) {
        pair<pair<int, int>, int>  tr;
        tr.first.first=u[j][i]+1, tr.first.second=d[j][i]-1, tr.second=i;
        if (vis2.find(tr)==vis2.end()) {
            col.push_back(tr);
            vis2.insert(tr);
        }
	}
	sort(row.begin(), row.end(), comp);
	sort(col.begin(), col.end(), comp);
	vector<rect> P, Q;
	for (int i=0; i<row.size(); i++) {
        if (i==0) {
            rect temp;
            temp.x1=row[i].second, temp.x2=row[i].second, temp.y1=row[i].first.first, temp.y2=row[i].first.second;
            P.push_back(temp);
        }
        else {
            if (row[i-1].first==row[i].first && row[i-1].second+1==row[i].second) P[P.size()-1].x2++;
            else {
                rect temp;
                temp.x1=row[i].second, temp.x2=row[i].second, temp.y1=row[i].first.first, temp.y2=row[i].first.second;
                P.push_back(temp);
            }
        }
	}
	for (int i=0; i<col.size(); i++) {
        if (i==0) {
            rect temp;
            temp.y1=col[i].second, temp.y2=col[i].second, temp.x1=col[i].first.first, temp.x2=col[i].first.second;
            Q.push_back(temp);
        }
        else {
            if (col[i-1].first==col[i].first && col[i-1].second+1==col[i].second) Q[Q.size()-1].y2++;
            else {
                rect temp;
                temp.y1=col[i].second, temp.y2=col[i].second, temp.x1=col[i].first.first, temp.x2=col[i].first.second;
                Q.push_back(temp);
            }
        }
	}
	sort(P.begin(), P.end(), comp1);
	sort(Q.begin(), Q.end(), comp2);
	/*printf("\n");
	for (auto i : P) printf("%d %d %d %d\n", i.x1, i.x2, i.y1, i.y2);
	printf("\n");
	for (auto i : Q) printf("%d %d %d %d\n", i.x1, i.x2, i.y1, i.y2);
	printf("\n");*/
    int left, right, mid, p, q;
	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) {
        left=0, right=P.size()-1;
        while (1) {
            if (left>=right) break;
            mid=(left+right)/2;
            if (com1(P[mid+1], l[i][j]+1, r[i][j]-1, u[i][j]+1)) left=mid+1;
            else right=mid;
        }
        p=left;
        left=0, right=Q.size()-1;
        while (1) {
            if (left>=right) break;
            mid=(left+right)/2;
            if (com2(Q[mid+1], u[i][j]+1, d[i][j]-1, l[i][j]+1)) left=mid+1;
            else right=mid;
        }
        q=left;
        //printf("::%d %d :: %d %d\n", i, j, p, q);
        if (P[p].y1==l[i][j]+1 && P[p].y2==r[i][j]-1 && P[p].x1<=u[i][j]+1 && P[p].x2>=d[i][j]-1 && Q[q].x1==u[i][j]+1 && Q[q].x2==d[i][j]-1 && Q[q].y1<=l[i][j]+1 && Q[q].y2>=r[i][j]-1) {
            pair<int, int> temp;
            temp.first=p, temp.second=q;
            if (ans_vis.find(temp)==ans_vis.end()) {
                ans++;
                ans_vis.insert(temp);
            }
        }
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:117:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for (int i=0; i<row.size(); i++) {
      |                ~^~~~~~~~~~~
rect.cpp:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |  for (int i=0; i<col.size(); i++) {
      |                ~^~~~~~~~~~~
rect.cpp:48:6: warning: unused variable 'idx' [-Wunused-variable]
   48 |  int idx, z;
      |      ^~~
rect.cpp:48:11: warning: unused variable 'z' [-Wunused-variable]
   48 |  int idx, z;
      |           ^

• 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