Submission #1045463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045463		vjudge1	Rectangles (IOI19_rect)	C++17	49 / 100	4836 ms	131272 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
set<int>pos[701][701];
long long count_rectangles(std::vector<std::vector<int> > a) {
    int n=a.size(),m=a[0].size();
    int ans=0;
    for(int i=1;i<n-1;i++){
        stack<int>stk;
        stk.push(m-1);
        for(int j=m-1;j--;){
            while(stk.size()&&a[i][j]>a[i][stk.top()])
                pos[i][j+1].insert(stk.top()-1),stk.pop();
            if(stk.size()){
                pos[i][j+1].insert(stk.top()-1);
                if(a[i][stk.top()]==a[i][j])
                    stk.pop();
            }
            stk.push(j);
            pos[i][j+1].erase(j);
        }
    }
    for(int r1=1;r1<n-1;r1++){
        vector<set<int>>stuf(m);
        vector<int>mx(m,0);
        for(int i=1;i<m-1;i++)
            stuf[i]=pos[r1][i];
        for(int r2=r1;r2<n-1;r2++){
            vector<int>sz(m);
            for(int i=m-1;--i;){
                set<int>st;
                for(auto y:stuf[i])
                    if(pos[r2][i].count(y))
                        st.insert(y);
                stuf[i]=st;
                mx[i]=max(mx[i],a[r2][i]);
                sz[i]=(1+sz[i+1])*(mx[i]<min(a[r1-1][i],a[r2+1][i]));
                if(!sz[i]) continue;
                ans+=distance(st.begin(),st.lower_bound(i+sz[i]));
            }
        }
    }
    return ans;
}

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