Submission #867568

#	Time	Username	Problem	Language	Result	Execution time	Memory
867568		JakobZorz	Rectangles (IOI19_rect)	C++14	37 / 100	5023 ms	1048576 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 cmp1(pair<int,int>&a,pair<int,int>&b){
    if(a.first!=b.first)
        return a.first>b.first;
    return a.second>b.second;
}

bool cmp2(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(),cmp1);
    set<int>s;
    for(auto [_val,i]:vals){
        auto iter=s.insert(i).first;
        auto next=iter;
        next++;
        
        if(next!=s.end()){
            if(*next-i-1!=0)
                gaps_down[x][i].insert(*next-i-1);
        }
    }
    
    sort(vals.begin(),vals.end(),cmp2);
    s.clear();
    for(auto [_val,i]:vals){
        auto iter=s.insert(i).first;
        auto prev=iter;
        if(prev!=s.begin()){
            prev--;
            if(i-*prev-1!=0)
                gaps_down[x][*prev].insert(i-*prev-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(),cmp1);
    set<int>s;
    for(auto [_val,i]:vals){
        s.insert(i);
        auto iter=s.find(i);
        auto next=iter;
        next++;
        
        if(next!=s.end()){
            if(*next-i-1!=0)
                gaps_right[i][y].insert(*next-i-1);
        }
    }
    
    sort(vals.begin(),vals.end(),cmp2);
    s.clear();
    for(auto [_val,i]:vals){
        auto iter=s.insert(i).first;
        auto prev=iter;
        if(prev!=s.begin()){
            prev--;
            if(i-*prev-1!=0)
                gaps_right[*prev][y].insert(i-*prev-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]);
    }
    ll res=0;
    int maxh=h-y;
    for(int y2=y;y2<h;y2++){
        if(gaps_right[x-1][y2].find(width)==gaps_right[x-1][y2].end()){
            maxh=y2-y;
            break;
        }
    }
    for(int height:s)
        if(height<=maxh)
            res++;
    /*for(int height:s){
        bool valid=true;
        for(int y2=y;y2<y+height;y2++){
            if(gaps_right[x-1][y2].find(width)==gaps_right[x-1][y2].end()){
                valid=false;
                break;
            }
        }
        
        if(valid)
            res++;
    }*/
    //cout<<"x: "<<x<<", y: "<<y<<", width: "<<width<<": "<<res<<"\n";
    return res;
}

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 'void process_column(int)':
rect.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [_val,i]:vals){
      |              ^
rect.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for(auto [_val,i]:vals){
      |              ^
rect.cpp: In function 'void process_row(int)':
rect.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for(auto [_val,i]:vals){
      |              ^
rect.cpp:86:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |     for(auto [_val,i]:vals){
      |              ^
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:145:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  145 |     for(int x=1;x<w-1;x++)
      |     ^~~
rect.cpp:150:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  150 |  return res;
      |  ^~~~~~

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