Submission #1060141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060141		Unforgettablepl	Rectangles (IOI19_rect)	C++17	37 / 100	5084 ms	28928 KiB

rect

#pragma GCC optimize("Ofast","unroll-all-loops")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;


long long count_rectangles(vector<vector<int>> a){
	int n = a.size();
	int m = a[0].size();
	long long ans = 0;
	for(int i=0;i<m;i++) {
		vector<int> maxi(n);
		vector allowedranges(n,vector(n,0));
		for(int j=i+1;j<m-1;j++) {
			stack<pair<int,int>> s;
			int last_voilater = -1;
			for(int k=0;k<n;k++) {
				maxi[k]=max(maxi[k],a[k][j]);
				if(k!=0 and (maxi[k-1]>=a[k-1][i] or maxi[k-1]>=a[k-1][j+1]))last_voilater=k-1;
				while(!s.empty() and s.top().first<a[k][j])s.pop();
				if(s.empty()) {
					s.emplace(a[k][j],k);
					continue;
				}
				const int l = s.top().second;
				s.emplace(a[k][j],k);
				const int r = k;
				if(r==l+1)continue;
				allowedranges[l][r]++;
				if(l<last_voilater)continue;
				if(allowedranges[l][r]==j-i)ans++;
			}
			s = stack<pair<int,int>>();
			last_voilater = n;
			for(int k=n-1;k>=0;k--) {
				if(k!=n-1 and (maxi[k+1]>=a[k+1][i] or maxi[k+1]>=a[k+1][j+1]))last_voilater=k+1;
				while(!s.empty() and s.top().first<a[k][j])s.pop();
				if(s.empty() or s.top().first==a[k][j]) {
					s.emplace(a[k][j],k);
					continue;
				}
				const int r = s.top().second;
				s.emplace(a[k][j],k);
				const int l = k;
				if(r==l+1)continue;
				allowedranges[l][r]++;
				if(last_voilater<r)continue;
				if(allowedranges[l][r]==j-i)ans++;
			}
		}
	}
	return ans;
}

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