Submission #867564

#	Time	Username	Problem	Language	Result	Execution time	Memory
867564		JakobZorz	Rectangles (IOI19_rect)	C++17	0 / 100	416 ms	698100 KiB

rect

#include"rect.h"
#include<algorithm>
#include<unordered_set>
#include<set>
#include<iostream>
using namespace std;
typedef long long ll;

unordered_set<int>intersect(unordered_set<int>&a,unordered_set<int>&b){
    if(a.size()>b.size())
        return intersect(b,a);
    unordered_set<int>res;
    for(int i:a)
        if(b.find(i)!=b.end())
            res.insert(i);
    return res;
}

unordered_set<int>gaps_right[2500][2500];
unordered_set<int>gaps_down[2500][2500];
int arr[2500][2500];
int w,h;

bool cmp(pair<int,int>&a,pair<int,int>&b){
    if(a.first!=b.first)
        return a.first>b.first;
    return a.second>b.second;
}

void process_column(int x){
    vector<pair<int,int>>vals(h);
    for(int y=0;y<h;y++)
        vals[y]={arr[x][y],y};
    sort(vals.begin(),vals.end(),cmp);
    set<int>s;
    for(auto [_val,i]:vals){
        auto iter=s.insert(i).first;
        auto next=iter,prev=iter;
        next++;
        if(prev!=s.begin()){
            prev--;
            if(i-*prev-1!=0)
                gaps_down[x][*prev].insert(i-*prev-1);
        }
        
        if(next!=s.end()){
            if(*next-i-1!=0)
                gaps_down[x][i].insert(*next-i-1);
        }
    }
}

void process_row(int y){
    vector<pair<int,int>>vals(w);
    for(int x=0;x<w;x++)
        vals[x]={arr[x][y],x};
    sort(vals.begin(),vals.end(),cmp);
    set<int>s;
    for(auto [_val,i]:vals){
        auto iter=s.insert(i).first;
        auto next=iter,prev=iter;
        next++;
        if(prev!=s.begin()){
            prev--;
            if(i-*prev-1!=0)
                gaps_right[*prev][y].insert(i-*prev-1);
        }
        
        if(next!=s.end()){
            if(*next-i-1!=0)
                gaps_right[i][y].insert(*next-i-1);
        }
    }
}

ll count(int x,int y,int width){
    unordered_set<int>s=gaps_down[x][y-1];
    for(int i=0;i<width;i++){
        s=intersect(s,gaps_down[x+i][y-1]);
    }
    //cout<<"x: "<<x<<", y: "<<y<<", width: "<<width<<": "<<s.size()<<"\n";
    return s.size();
}

ll count_rectangles(vector<vector<int>>a_){
    h=(int)a_.size();
    w=(int)a_[0].size();
    for(int x=0;x<w;x++){
        for(int y=0;y<h;y++){
            arr[x][y]=a_[y][x];
        }
    }
    
    for(int x=0;x<w;x++)
        process_column(x);
    
    for(int y=0;y<h;y++)
        process_row(y);
    
    ll res=0;
    for(int x=1;x<w-1;x++)
        for(int y=1;y<h-1;y++)
            for(int width:gaps_right[x-1][y])
                res+=count(x,y,width);
    
	return res;
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:101:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  101 |     for(int x=1;x<w-1;x++)
      |     ^~~
rect.cpp:106:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  106 |  return res;
      |  ^~~~~~

• 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