Submission #623543

#	Time	Username	Problem	Language	Result	Execution time	Memory
623543		AbdelmagedNour	Rectangles (IOI19_rect)	C++17	50 / 100	5078 ms	190848 KiB

rect

#include<bits/stdc++.h>
using namespace std;
#include "rect.h"
//#include"grader.cpp"
int nxt[2505][2505],prv[2505][2505];
long long count_rectangles(vector<vector<int>>a) {
	int n=a.size();
	int m=a[0].size();
	if(n<3||m<3)return 0;
	vector<vector<pair<int,int>>>v(n);
	for(int i=1;i<n-1;i++){
        vector<int>pos;
        for(int j=m-1;j>=0;j--){
            while(!pos.empty()&&a[i][pos.back()]<a[i][j]){
                v[i].push_back({j,pos.back()});
                pos.pop_back();
            }
            if(!pos.empty())v[i].push_back({j,pos.back()});
            nxt[i][j]=(pos.empty()?5000:pos.back());
            pos.push_back(j);
        }
        pos.clear();
        for(int j=0;j<m;j++){
            while(!pos.empty()&&a[i][pos.back()]<a[i][j])pos.pop_back();
            prv[i][j]=(pos.empty()?-1:pos.back());
            pos.push_back(j);
        }
	}
	long long res=0;
	for(int i=1;i<n-1;i++){
        for(auto[st,en]:v[i]){
            if(en-st==1){
                continue;
            }
            int mx[en-st+5]={};
            memset(mx,-1,sizeof(mx));
            for(int dep=0;i+dep<n-1;dep++){
                if(nxt[i+dep][st]<en||prv[i+dep][en]>st){
                    break;
                }
                int cnt=0,flag=1;
                for(int j=st+1;j<en&&flag;j++){
                    mx[j-st]=max(mx[j-st],a[i+dep][j]);
                    if(mx[j-st]>=a[i-1][j])flag=0;
                }
                if(!flag){
                    break;
                }
                for(int j=st+1;j<en;j++)cnt+=mx[j-st]>=a[i+dep+1][j];
                if(cnt==0)res++;
            }
        }
	}
	return res;
}

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