Submission #404069

#	Time	Username	Problem	Language	Result	Execution time	Memory
404069		Everule	Rectangles (IOI19_rect)	C++17	100 / 100	1905 ms	437056 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
long long count_rectangles(std::vector<std::vector<int> > a) {
    int n = a.size(), m = a[0].size();
	vector hr(m, vector(m, vector(0,pair(0, 0))));
    vector vr(n, vector(m, pair(pair(-100000000,0), pair(100000000,0))));
    for(int i=1;i<n-1;i++){
        stack<int> stk;
        for(int j=0;j<m;j++){
            while(!stk.empty()){
                int k = stk.top();
                if(hr[k][j].empty() || hr[k][j].back().second + 1 != i){
                    hr[k][j].emplace_back(i,i);
                }
                else{
                    hr[k][j].back().second++;
                }
                if(a[i][k] <= a[i][j]){
                    stk.pop();
                }
                if(a[i][k] >= a[i][j]){
                    break;
                }
            }
            stk.push(j);
        }
    }
    /*
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<i<<" "<<j<<"\n";
            for(auto &[l,r] : hr[i][j]){
                cout<<l<<" "<<r<<"\n";
            }
            cout<<"\n\n";
        }
    }
    */
    for(int j=m-1;j>=0;--j){
        stack<int> stk;
        for(int i=0;i<n;i++){
            while(!stk.empty()){
                int k = stk.top();
                if(a[k][j] <= a[i][j]){
                    vr[k][j].second.first = i;
                    int lf = j;
                    if(j < m-1 && vr[k][j+1].second.first == i){
                        lf = max(lf, vr[k][j+1].second.second);
                    }
                    if(j < m-1 && vr[i][j+1].first.first == k){
                        lf = max(lf, vr[i][j+1].first.second);
                    }
                    vr[k][j].second.second = lf;
                }
                else{
                    vr[i][j].first.first = k;
                    int lf = j;
                    if(j < m-1 && vr[k][j+1].second.first == i){
                        lf = max(lf, vr[k][j+1].second.second);
                    }
                    if(j < m-1 && vr[i][j+1].first.first == k){
                        lf = max(lf, vr[i][j+1].first.second);
                    }
                    vr[i][j].first.second = lf;
                }
                if(a[k][j] <= a[i][j]){
                    stk.pop();
                }
                if(a[k][j] >= a[i][j]){
                    break;
                }
            }
            stk.push(i);
        }
    }
    /*for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<i<<" "<<j<<"\n";
            cout<<vr[i][j].first.first<<" "<<vr[i][j].first.second<<" "<<vr[i][j].second.first<<" "<<vr[i][j].second.second<<"\n";
        }
    }
    cout<<"\n\n";
    */
    ll ans = 0;
    for(int i=0;i<m;i++){
        for(int j=i+2;j<m;j++){
            for(auto &[l,r] : hr[i][j]){
                for(int k=max(l-1,0);k<=min(r+1,n-1);k++){
                    auto [l1,d1] = vr[k][i+1].first;
                    auto [r2,d2] = vr[k][i+1].second;
                    if(l <= l1 + 1 && l1 + 1 < k && d1 >= j-1){
                        //cout<<i<<" "<<j<<" "<<l1<<" "<<k<<"\n";
                        ans++;
                    }
                    if(r2 - 1 <= r && k < r2 - 1 && d2 >= j-1){
                        //cout<<i<<" "<<j<<" "<<k<<" "<<r2<<"\n";
                        ans++;
                    }
                }
            }
        }
    }
    return ans;
}

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