Submission #402314

#	Time	Username	Problem	Language	Result	Execution time	Memory
402314		b00n0rp	Rectangles (IOI19_rect)	C++17	59 / 100	3118 ms	1048580 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define FORD(i,a,b) for(int i = a; i >= b; i --)
#define pii pair<int,int>
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
 
const ll MX = 2505;
 
ll ans = 0;
int n,m; 
int gl[MX][MX],gr[MX][MX],gu[MX][MX],gd[MX][MX];
pii rows[MX][MX],cols[MX][MX];
vector<pair<ll,int> > row_map,col_map;
vector<pair<ll,ll> > quer_row,quer_col;
bitset<MX*MX*6> b1,b2;
vi gg[MX][MX];

int compvar(const void *one, const void *two)
{
    int a = *((int*)one);
    int b = *((int*)two);
    if (a<b)
       return -1;
    if (a == b)
       return 0;
    return 1;   

}
 
void check_rectangle(int x1,int y1,int x2,int y2,int q){
    quer_row.pb({(y1-1)*MX*MX+(y2+1)*MX+x1,q*MX+x2});
    quer_col.pb({(x1-1)*MX*MX+(x2+1)*MX+y1,q*MX+y2});
}
 
ll count_rectangles(vector<vi> a){
    n = a.size();
    m = a[0].size();
    if(n <= 2 or m <= 2) return 0;
    FORD(i,n-1,0){
        stack<int> st;
        REP(j,m){
            gl[i][j] = gr[i][j] = gu[i][j] = gd[i][j] = -1;
        }
        REP(j,m){
            while(st.size() and a[i][st.top()] <= a[i][j]){
                gr[i][st.top()] = j;
                st.pop();
            }
            st.push(j);
        }
        while(!st.empty()) st.pop();
        FORD(j,m-1,0){
            while(st.size() and a[i][st.top()] <= a[i][j]){
                gl[i][st.top()] = j;
                st.pop();
            }
            st.push(j);
        }
        REP(j,m){
            if(gr[i][j] != -1 and gr[i][j] != j+1){
                ll val = j*MX*MX+gr[i][j]*MX+i;
                if(rows[j][gr[i][j]].F == i+1){
                	rows[j][gr[i][j]].F--;
                }
                else{
					rows[j][gr[i][j]] = {i,i};
                }
                row_map.pb({val,rows[j][gr[i][j]].S});
            }
            if(gl[i][j] != -1 and gl[i][j] != j-1 and gr[i][gl[i][j]] != j){
                ll val = gl[i][j]*MX*MX+j*MX+i;
                if(rows[gl[i][j]][j].F == i+1){
                	rows[gl[i][j]][j].F--;
                }
                else{
					rows[gl[i][j]][j] = {i,i};
                }
                row_map.pb({val,rows[gl[i][j]][j].S});
            }
        }
    }
    FORD(j,m-1,0){
        stack<int> st;
        REP(i,n){
            while(st.size() and a[st.top()][j] <= a[i][j]){
                gd[st.top()][j] = i;
                st.pop();
            }
            st.push(i);
        }
        while(!st.empty()) st.pop();
        FORD(i,n-1,0){
            while(st.size() and a[st.top()][j] <= a[i][j]){
                gu[st.top()][j] = i;
                st.pop();
            }
            st.push(i);
        }
        REP(i,n){
            if(gd[i][j] != -1 and gd[i][j] != i+1){
                ll val = i*MX*MX+gd[i][j]*MX+j;
                if(cols[i][gd[i][j]].F == j+1){
                	cols[i][gd[i][j]].F--;
                }
                else{
					cols[i][gd[i][j]] = {j,j};
                }
                col_map.pb({val,cols[i][gd[i][j]].S});
            }
            if(gu[i][j] != -1 and gu[i][j] != i-1 and gd[gu[i][j]][j] != i){
                ll val = gu[i][j]*MX*MX+i*MX+j;
                if(cols[gu[i][j]][i].F == j+1){
                	cols[gu[i][j]][i].F--;
                }
                else{
					cols[gu[i][j]][i] = {j,j};
                }
                col_map.pb({val,cols[gu[i][j]][i].S});
            }
        }
    }
    vector<ll> bruh;
    FOR(i,1,n-1){
        FOR(j,1,m-1){
            // topleft
            if(gr[i][j-1] != -1 and gd[i-1][j] != -1){
            	gg[i][j].pb((gd[i-1][j]-1)*MX+gr[i][j-1]-1);
            }
            // topright
            if(gl[i][j+1] != -1 and gd[i-1][j] != -1){
                gg[i][(gl[i][j+1]+1)].pb((gd[i-1][j]-1)*MX+j);
            }
            // bottomleft
            if(gr[i][j-1] != -1 and gu[i+1][j] != -1){
            	gg[(gu[i+1][j]+1)][j].pb((i)*MX+gr[i][j-1]-1);
            }
            // bottomright
            if(gl[i][j+1] != -1 and gu[i+1][j] != -1){
            	gg[(gu[i+1][j]+1)][(gl[i][j+1]+1)].pb((i)*MX+j);
            }
            // clockwise
            if(gr[i][j-1] != -1 and gd[i-1][gr[i][j-1]-1] != -1){
            	gg[i][j].pb((gd[i-1][gr[i][j-1]-1]-1)*MX+gr[i][j-1]-1);
            }
            // anti-clockwise
            if(gl[i][j+1] != -1 and gd[i-1][gl[i][j+1]+1] != -1){
            	gg[i][(gl[i][j+1]+1)].pb((gd[i-1][gl[i][j+1]+1]-1)*MX+j);
            }
        }
    }
    ll last = -1;
    int q = 0;
    FOR(i,1,n-1){
    	FOR(j,1,m-1){
    		if(SZ(gg[i][j]) > 1){
    			sort(all(gg[i][j]));
    		}
    		for(auto x:gg[i][j]){
    			ll val = i*MX*MX*MX+j*MX*MX+x;
    			if(val == last) continue;
    			last = val;
    			check_rectangle(i,j,x/MX,x%MX,q);
    			q++;
    		}
    	}
    }
    sort(all(quer_col));
    sort(all(quer_row));
    sort(all(col_map));
    sort(all(row_map));
    int cur = 0;
    for(auto x:col_map){
    	while(cur < q and quer_col[cur].F < x.F) cur++;
    	while(cur < q and quer_col[cur].F == x.F){
    		if(quer_col[cur].S%MX <= x.S) b1[quer_col[cur].S/MX] = 1;
    		cur++;
    	}
    }
    cur = 0;
    for(auto x:row_map){
    	while(cur < q and quer_row[cur].F < x.F) cur++;
    	while(cur < q and quer_row[cur].F == x.F){
    		if(quer_row[cur].S%MX <= x.S) b2[quer_row[cur].S/MX] = 1;
    		cur++;
    	}
    }
    REP(i,q){
    	if(b1[i] and b2[i]) ans++;
    }
    // cout << ((double)clock() / CLOCKS_PER_SEC) << "\n";
    return ans;
}

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