Submission #1060145

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
10601452024-08-15 10:58:34UnforgettableplRectangles (IOI19_rect)C++17
59 / 100
5092 ms28696 KiB
#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;
vector allowedranges(n,vector(n,0));
for(int i=0;i<m;i++) {
vector<int> maxi(n);
for(auto&j:allowedranges)fill(j.begin(), j.end(),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]++;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...