Submission #298381

#	Time	Username	Problem	Language	Result	Execution time	Memory
298381		Abelyan	Rectangles (IOI19_rect)	C++17	0 / 100	220 ms	305580 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

//#pragma GCC target("avx2")
//#pragma GCC optimization("unroll-loops")
//#pragma GCC optimize("O2")
//#pragma GCC optimize("O3")

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define make_unique(v) v.erase(unique(all(v)),v.end())


const int N=2506;
vector<int> ver[N][N],bn[N][N];
int en[N][N], sk[N][N];

long long count_rectangles(vector<vector<int> > a) {

	int n=a.size();
	int m=a[0].size();
	FORT(j,1,m-2){
		stack<pir> s;
		s.push({INT_MAX,-1});
		int qan=0;
		FOR(i,n){
			while(s.top().fr<=a[i][j]){
				if (s.top().sc==i-1){
					s.pop();
					continue;
				}
				ver[i-1][j].ad(s.top().sc+1);
				bn[i-1][s.top().sc+1].ad(j);
				qan++;
				
				s.pop();
			}
			s.push({a[i][j],i});
		}
		while(s.size()!=1)s.pop();
		assert(s.top().fr==INT_MAX);
		FORD(i,n){
			while(s.top().fr<a[i][j]){
				if (s.top().sc==i+1){
					s.pop();
					continue;
				}
				ver[s.top().sc-1][j].ad(i+1);
				bn[s.top().sc-1][i+1].ad(j);
				qan++;
				s.pop();

			}
			s.push({a[i][j],i});

		}
		/*
		if (a[0][j]>a[1][j] && a[2][j]>a[1][j]);
		else assert(qan==0);*/
	}
	ll ans=0;
	FORT(i,1,n-2){
		stack<pir> s;
		s.push({INT_MAX,-1});
		FOR(j,m){
			while(s.top().fr<=a[i][j]){
				
				//cout<<i<<" hey "<<s.top().fr<<" "<<s.top().sc<<" "<<a[i][j]<<endl;
				if (s.top().sc==j-1){
					s.pop();
					continue;
				}
				int l=s.top().sc+1,r=j-1;
				
				//cout<<i<<" "<<l<<" "<<r<<" "<<sk[l][r]<<" "<<en[l][r]<<endl;
				if (en[l][r]!=i-1){
					sk[l][r]=i;
				}
				en[l][r]=i;
				trav(to,ver[i][l]){
					if (to<sk[l][r])continue;
					if (upper_bound(all(bn[i][to]),r)-lower_bound(all(bn[i][to]),l)==r-l+1)ans++;
				}
				s.pop();
			}
			s.push({a[i][j],j});
		}
		while(s.size()!=1)s.pop();
		FORD(j,m){
			while(s.top().fr<a[i][j]){
				//cout<<i<<" "<<s.top().fr<<" "<<s.top().sc<<" "<<a[i][j]<<endl;
				if (s.top().sc==j+1){
					s.pop();
					continue;
				}
				int l=j+1,r=s.top().sc-1;
				
				//cout<<"hey "<<i<<" "<<l<<" "<<r<<" "<<sk[l][r]<<" "<<en[l][r]<<endl;
				if (en[l][r]!=i-1){
					sk[l][r]=i;
				}
				en[l][r]=i;
				trav(to,ver[i][r]){
					if (to<sk[l][r])continue;
					if (upper_bound(all(bn[i][to]),r)-lower_bound(all(bn[i][to]),l)==r-l+1)ans++;
				}
				s.pop();
			}
			s.push({a[i][j],j});
		}
	}
	return ans;
}

• 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