Submission #291212

#	Time	Username	Problem	Language	Result	Execution time	Memory
291212		thebes	Rectangles (IOI19_rect)	C++14	100 / 100	2454 ms	863948 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define F first
#define S second

const int MN = 2505, MM = 15e6;
int N, M, C, i, j, x, y, h[MM], hp[MM], cnt, pre[MN], ds[MN], nxt[MN]; ll ans;
pii bnd[MM]; vi vec[MN], adj[MM], hid[MN];
vector<pii> evt[MN];
pii hist[MN][MN];
stack<pii> stk;
vector<pii> st[MN];

inline void process(vi vec,int x,bool col){
    C = (int)vec.size();
    for(int i=0;i<=C;i++) st[i].clear();
    while(stk.size()) stk.pop();
    int flg;
    for(int i=0;i<C;i++){
        flg = 0;
        while(stk.size()){
            if(stk.top().S+1<i&&!flg){
                if(col) evt[i-1].push_back({x,stk.top().S+1});
                else{
                    bnd[++cnt] = {stk.top().S+1,i-1};
                    h[cnt] = x;
                    st[stk.top().S+1].push_back({i-1,cnt});
                }
            }
            if(stk.top().F==vec[i]) flg=1;
            if(stk.top().F<=vec[i]) stk.pop();
            else break;
        }
        stk.push({vec[i],i});
    }
    while(stk.size()) stk.pop();
    for(int i=0;i<=C;i++){
        reverse(st[i].begin(),st[i].end());
        for(auto v : st[i]){
            while(stk.size()){
                if(stk.top().F<v.F) stk.pop();
                else break;
            }
            if(stk.size()){
                adj[stk.top().S].push_back(v.S);
                hp[v.S] = 1;
            }
            stk.push(v);
        }
    }
}

vi res;

inline void mrg(int x,int y){
    if(x^y){
        res.clear();
        if(vec[x].empty()||vec[y].empty()){
            vec[x].clear(); vec[y].clear();
            return;
        }
        if(vec[x].size()>vec[y].size()) swap(x,y);
        for(int i=0,j=0;i<(int)vec[x].size();i++){
            while(j+1<(int)vec[y].size()&&vec[y][j]<vec[x][i]) j++;
            if(j<vec[y].size()&&vec[x][i]==vec[y][j]) res.push_back(vec[x][i]);
        }
        vec[min(x,y)].clear();
        vec[max(x,y)]=res;
    }
}

int fnd(int x){return ds[x]=ds[x]==x?x:fnd(ds[x]);}

void dfs(int n){
    for(auto v : adj[n]) dfs(v);
    for(auto v : adj[n]) mrg(bnd[v].S, bnd[n].S);
    int it = fnd(bnd[n].F);
    while(it<M&&it<=bnd[n].S){
        mrg(it,bnd[n].S);
        ds[fnd(it)]=fnd(it+1);
        it = fnd(it);
    }
    int p = upper_bound(vec[bnd[n].S].begin(),vec[bnd[n].S].end(),h[n])-vec[bnd[n].S].begin();
    ans += vec[bnd[n].S].size()-p;
}

long long count_rectangles(vector<vector<int>> a){
    vi col;
	N = a.size(), M = a[0].size();
	memset(hist,-1,sizeof(hist));
	for(i=0;i<M;i++){
        col.clear();
        for(j=0;j<N;j++) col.push_back(a[j][i]);
        process(col,i,1);
	}
	memset(hist,-1,sizeof(hist));
	for(i=0;i<N;i++)
        process(a[i],i,0);
	for(i=1;i<=cnt;i++){
        hid[h[i]].push_back(i);
	}
	memset(hist,-1,sizeof(hist));
	for(i=0;i<N;i++){
        for(j=0;j<M;j++) vec[j].clear(), ds[j]=j;
        for(auto v : evt[i]) vec[v.F].push_back(v.S);
        for(j=0;j<M;j++) sort(vec[j].begin(),vec[j].end());
        for(auto v : hid[i]){
            if(hist[bnd[v].F][bnd[v].S].F==i) h[v] = hist[bnd[v].F][bnd[v].S].S+1;
            else h[v] = 1;
            hist[bnd[v].F][bnd[v].S]={i+1,h[v]};
            h[v] = i-h[v];
        }
        for(auto v : hid[i]){
            if(hp[v]) continue;
            dfs(v);
        }
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'void mrg(int, int)':
rect.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             if(j<vec[y].size()&&vec[x][i]==vec[y][j]) res.push_back(vec[x][i]);
      |                ~^~~~~~~~~~~~~~

• 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