Submission #1045880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045880		vjudge1	Rectangles (IOI19_rect)	C++17	0 / 100	1 ms	860 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
set<int>pos[31][31],pos2[31][31];
set<int> operator & (const set<int>&a,const set<int>&b){
    set<int>c;
    if(a.size()<b.size()){
        for(auto i:a)
            if(b.count(i))
                c.insert(i);
    } else for(auto i:b)
        if(a.count(i))
            c.insert(i);
    return c;
}
set<int>stb[31][31];
int cnt(int l,int r){
    set<int>res=stb[l][0];
    for(int i=l;i++<r;)
        res=res&stb[i][0];
    return res.size();
}
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 j=1;j<m-1;j++){
        stack<int>stk;
        stk.push(n-1);
        for(int i=n-1;i--;){
            while(stk.size()&&a[i][j]>a[stk.top()][j])
                pos2[i+1][j].insert(stk.top()-1),stk.pop(); 
            if(stk.size()){
                pos2[i+1][j].insert(stk.top()-1);
                if(a[stk.top()][j]==a[i][j])
                    stk.pop();
            }
            stk.push(i);
            pos2[i+1][j].erase(i);
        }
    }
    for(int col=1;col<m-1;col++){
        for(int i=1;i<n-1;i++)
            stb[i][0]=pos[i][col];
        for(int row1=1;row1<n-1;row1++)
            for(auto row2:pos2[row1][col])
                ans+=cnt(row1,row2);
    }
    return ans;
}

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