Submission #827104

#	Time	Username	Problem	Language	Result	Execution time	Memory
827104		vjudge1	Rectangles (IOI19_rect)	C++17	10 / 100	5020 ms	37288 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
#define f first
#define s second 
#define ent '\n'
//#define int long long

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

//typedef long double ld;
typedef long long ll;
using namespace std;
 
struct node{double x,y;};
//double len(node a,node b)
//{return sqrt((a.x-b.x)*(a.x-b.y)+(a.y-b.y)*(a.x-b.y));}

struct seg{
	int m1,m2,sum,cnt;
};

const string out[2]={"No\n","Yes\n"};
const ll dx[]={0,0,1,-1,-1,1,1,-1};  
const ll dy[]={1,-1,0,0,-1,1,-1,1};
const int md=998244353;
const int mod=1e9+7;
const int mx=3e3+1; 
const int tst=1e5;
const bool T=0;

int a[mx][mx];
int d[mx];
int b[mx];
int n,m,k;

long long count_rectangles(vector<vector<int> > t){
	n=t.size();
	m=t[0].size();
	if(min(n,m)<3){
		return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=t[i-1][j-1];
		}
	}
	ll ans=0;
	if(n==3){
		for(int i=2;i<m;i++){
			int mx=0;
			for(int j=i;j<m;j++){
				if(a[2][j]>=min(a[1][j],a[3][j])){
					break;
				}
				mx=max(mx,a[2][j]);
				if(mx<min(a[2][i-1],a[2][j+1])){
					ans++;
				}
			}
		}
		return ans;
	}
	for(int l=2;l<n;l++){
		for(int r=l;r<n;r++){
			int t=ans;
			for(int i=1;i<=m;i++){
				int mx=0;
				if(l==r){
					b[i]=a[r][i];
				}
				else{
					b[i]=max(b[i],a[r][i]);
				}
			}
			for(int i=2;i<m;i++){
				for(int j=i;j<m;j++){
					if(b[j]>=min(a[l-1][j],a[r+1][j])){
						break;
					}
					bool ok=1;
					for(int k=l;k<=r;k++){
						if(i==j){
							d[k]=0;
						}
						d[k]=max(d[k],a[k][j]);
						if(d[k]>=min(a[k][i-1],a[k][j+1])){
							ok=0; break;
						}
					}
					ans+=ok;
				}
			}
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:68:9: warning: unused variable 'mx' [-Wunused-variable]
   68 |     int mx=0;
      |         ^~
rect.cpp:66:8: warning: unused variable 't' [-Wunused-variable]
   66 |    int t=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