Submission #294661

#	Time	Username	Problem	Language	Result	Execution time	Memory
294661		TheLorax	Rectangles (IOI19_rect)	C++14	0 / 100	1 ms	512 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

#define F first
#define S second
#define MT make_tuple
#define MP make_pair
#define SZ(a) ((int)(a).size())
#define PB push_back
#define ALL(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;

int n, m;

bool valid(std::vector<std::vector<int> > &a, int i, int j){
	if(i<1 || i>n-2 || j<1 || j>m-2)
		return 0;
	return min(min(a[i+1][j],a[i-1][j]),min(a[i][j+1],a[i][j-1]))>a[i][j];
}

ll cre(ll w, ll mx, ll mi){
	return (mx-mi)*(w+1)*w/2;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	n=SZ(a);
	m=SZ(a[0]);
	std::vector<std::vector<int> > p(n, std::vector<int> (m,0));
	for(int i=1; i<m-1; i++)
		if(valid(a,1,i))
			p[1][i]=1;
	for(int i=2; i<n-1; i++)
		for(int j=1; j<m-1; j++)
			if(valid(a,i,j))
				p[i][j]=p[i-1][j]+1;
	ll cc=0;
	for(int i=1; i<n-1; i++){
		std::vector<ii> s(m-2);
		std::vector<int> ne(m-2), pr(m-2);
		iota(ALL(ne),0);
		iota(ALL(pr),0);
		for(int j=0; j<SZ(s); j++)
			s[j]={p[i][j+1],j};
		sort(ALL(s));
		reverse(ALL(s));
		std::vector<int> td;
		for(int j=0; j<SZ(s); j++){
			if(j && s[j].F<s[j-1].F){
				while (!td.empty()){
					int x=td.back();
					cc+=cre(ne[x]-pr[x]-1,p[i][x],s[j].F);
					while (!td.empty() && td.back()>pr[x])
						td.pop_back();
				}
			}
			int x=s[j].S;
			td.PB(x);
			if(x<m-3 && ne[x+1]<m-2)
				ne[x]=ne[ne[x+1]];
			else
				ne[x]=m-2;
			if(x>0 && pr[x-1]>=0)
				pr[x]=pr[pr[x-1]];
			else
				pr[x]=-1;
		}
		while (!td.empty()){
			int x=td.back();
			cc+=cre(ne[x]-pr[x]-1,p[i][x],0);
			while (!td.empty() && td.back()>pr[x])
			td.pop_back();
		}
	}
	return cc;
}

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