Submission #535418

#	Time	Username	Problem	Language	Result	Execution time	Memory
535418		mario05092929	Rectangles (IOI19_rect)	C++14	100 / 100	3366 ms	718452 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e16;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,m,a[2505][2505];
int L[2505][2505],R[2505][2505],U[2505][2505],D[2505][2505];
stack <pi> s;
vec N[2505][2505],M[2505][2505];
vector <pair<pi,pi>> V;

void make_LRUD() {
	for(int i = 1;i <= n;i++) {
		s.push({INF,-1});
		for(int j = 1;j <= m;j++) {
			while(s.top().x <= a[i][j]) s.pop();
			L[i][j] = s.top().y;
			s.push({a[i][j],j});
		}
		while(!s.empty()) s.pop();
	}
	for(int i = 1;i <= n;i++) {
		s.push({INF,-1});
		for(int j = m;j >= 1;j--) {
			while(s.top().x <= a[i][j]) s.pop();
			R[i][j] = s.top().y;
			s.push({a[i][j],j});
		}
		while(!s.empty()) s.pop();
	}
	for(int i = 1;i <= m;i++) {
		s.push({INF,-1});
		for(int j = 1;j <= n;j++) {
			while(s.top().x <= a[j][i]) s.pop();
			U[j][i] = s.top().y;
			s.push({a[j][i],j});
		}
		while(!s.empty()) s.pop();
	}
	for(int i = 1;i <= m;i++) {
		s.push({INF,-1});
		for(int j = n;j >= 1;j--) {
			while(s.top().x <= a[j][i]) s.pop();
			D[j][i] = s.top().y;
			s.push({a[j][i],j});
		}
		while(!s.empty()) s.pop();
	}
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            int sx = U[i][j], sy = L[i][j], ex = D[i][j], ey = R[i][j];
            if(sx != -1&&ex != -1) N[sx][ex].pb(j);
            if(sy != -1&&ey != -1) M[sy][ey].pb(i);
        }
    }
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) sort(all(N[i][j])), N[i][j].erase(unique(all(N[i][j])),N[i][j].end());
    }
    for(int i = 1;i <= m;i++) {
        for(int j = 1;j <= m;j++) sort(all(M[i][j])), M[i][j].erase(unique(all(M[i][j])),M[i][j].end());
    }
}

ll 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++) a[i+1][j+1] = A[i][j];
    }
    make_LRUD();
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            int sx = U[i][j], sy = L[i][j], ex = D[i][j], ey = R[i][j];
            if(sx == -1||sy == -1||ex == -1||ey == -1) continue;
            int L = upper_bound(all(N[sx][ex]),sy)-N[sx][ex].begin();
            int R = lower_bound(all(N[sx][ex]),ey)-N[sx][ex].begin()-1;
            if(L == N[sx][ex].size()||R == -1||R-L != ey-sy-2) continue;
            L = upper_bound(all(M[sy][ey]),sx)-M[sy][ey].begin();
            R = lower_bound(all(M[sy][ey]),ex)-M[sy][ey].begin()-1;
            if(L == M[sy][ey].size()||R == -1||R-L != ex-sx-2) continue;
            V.pb({{sx,sy},{ex,ey}});
        }
    }
    sort(all(V)), V.erase(unique(all(V)),V.end());
    return V.size();
}

Compilation message (stderr)

rect.cpp:7: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    7 | #pragma gcc optimize("O3")
      | 
rect.cpp:8: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    8 | #pragma gcc optimize("Ofast")
      | 
rect.cpp:9: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    9 | #pragma gcc optimize("unroll-loops")
      | 
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             if(L == N[sx][ex].size()||R == -1||R-L != ey-sy-2) continue;
      |                ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             if(L == M[sy][ey].size()||R == -1||R-L != ex-sx-2) continue;
      |                ~~^~~~~~~~~~~~~~~~~~~

• 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