Submission #161815

#	Time	Username	Problem	Language	Result	Execution time	Memory
161815		andrew	Rectangles (IOI19_rect)	C++17	38 / 100	1422 ms	331216 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>


using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2510, M = 90;

int prv[N][N], nxt[N][N];
int prv1[N][N], nxt1[N][N];

int pos[N][N];
int p[N * N], kol[N * N], mxy[N * N], mnx[N * N], mxx[N * N], mny[N * N], id, zp[N * N], zapros;

int get(int x){
    if(p[x] != x)p[x] = get(p[x]);
    return p[x];
}

void unite(int a, int b){
    a = get(a), b = get(b);
    if(a == b)return;
    kol[a] += kol[b];
    mxx[a] = max(mxx[a], mxx[b]);
    mxy[a] = max(mxy[a], mxy[b]);
    mnx[a] = min(mnx[a], mnx[b]);
    mny[a] = min(mny[a], mny[b]);
    p[b] = a;
    return;
}

long long count_rectangles(vector<vector<int> > a) {
    ll n = a.size(), m = a[0].size();
    if(n < 3)return 0;
    if(n == 3){
        int ans = 0, mx = 0;
        for(int i = 1; i < m - 1; i++){
            mx = 0;
            for(int j = i; j < m - 1; j++){
                mx = max(mx, a[1][j]);
                if(a[0][j] <= a[1][j] || a[2][j] <= a[1][j])break;
                if(a[1][i - 1] > mx && mx < a[1][j + 1])ans++;
            }
        }
        return ans;
    }


    if(n <= 80 && m <= 80){
        for(int i = 0; i < n; i++){
            vector <pii> st;
            st.push_back({1e8, -1});

            for(int j = 0; j < m; j++){
                while(!st.empty() && st.back().fi < a[i][j])st.pop_back();
                prv[i][j] = st.back().se;
                st.push_back({a[i][j], j});
            }

            st.clear();
            st.push_back({1e8, m});

            for(int j = m - 1; j >= 0; j--){
                while(!st.empty() && st.back().fi < a[i][j])st.pop_back();
                nxt[i][j] = st.back().se;
                st.push_back({a[i][j], j});
            }
            st.clear();
        }
        for(int j = 0; j < m; j++){
            vector <pii> st;
            st.push_back({1e8, -1});

            for(int i = 0; i < n; i++){
                while(!st.empty() && st.back().fi < a[i][j])st.pop_back();
                prv1[i][j] = st.back().se;
                st.push_back({a[i][j], i});
            }

            st.clear();
            st.push_back({1e8, n});

            for(int i = n - 1; i >= 0; i--){
                while(!st.empty() && st.back().fi < a[i][j])st.pop_back();
                nxt1[i][j] = st.back().se;
                st.push_back({a[i][j], i});
            }
            st.clear();
        }
        int ans = 0;

        for(int r1 = 1; r1 < n - 1; r1++)
            for(int c1 = 1; c1 < m - 1; c1++)
            for(int r2 = r1; r2 < n - 1; r2++)
            for(int c2 = c1; c2 < m - 1; c2++){
                bool ok = 1;
                for(int i = c1; i <= c2; i++){
                    if(nxt1[r1 - 1][i] <= r2)ok = 0;
                }
                for(int i = c1; i <= c2; i++){
                    if(prv1[r2 + 1][i] >= r1)ok = 0;
                }
                for(int i = r1; i <= r2; i++){
                    if(nxt[i][c1 - 1] <= c2)ok = 0;
                }
                for(int i = r1; i <= r2; i++){
                    if(prv[i][c2 + 1] >= c1)ok = 0;
                }
                //if(ok)cout << r1 << " " << c1 << " " << r2 << " " << c2 << "\n";
                ans += ok;
            }
        return ans;
    }

    map < int, vector<pii> > v;

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)v[a[i][j]].push_back({i, j});

    ll res = 0;

    for(auto kek : v){
        for(auto j : kek.se){
            pos[j.fi][j.se] = ++id;
            //cout << j.fi << " " << j.se << "\n";
            p[id] = id;
            kol[id] = 1;
            mxx[id] = mnx[id] = j.fi;
            mxy[id] = mny[id] = j.se;
            if(j.fi > 0 && pos[j.fi - 1][j.se])unite(get(pos[j.fi][j.se]), get(pos[j.fi - 1][j.se]));
            if(j.fi < n - 1 && pos[j.fi + 1][j.se])unite(get(pos[j.fi][j.se]), get(pos[j.fi + 1][j.se]));
            if(j.se > 0 && pos[j.fi][j.se - 1])unite(get(pos[j.fi][j.se]), get(pos[j.fi][j.se - 1]));
            if(j.se < m - 1 && pos[j.fi][j.se + 1])unite(get(pos[j.fi][j.se]), get(pos[j.fi][j.se + 1]));
        }
        zapros++;
        for(auto j : kek.se)if(zp[get(pos[j.fi][j.se])] != zapros){
            zp[get(pos[j.fi][j.se])] = zapros;
            int cmp = get(pos[j.fi][j.se]);
            if((mxx[cmp] != n - 1 && mnx[cmp] && mny[cmp] && mxy[cmp] != m - 1) && (kol[cmp] == (mxx[cmp] - mnx[cmp] + 1) * (mxy[cmp] - mny[cmp] + 1))){
                res++;
                //cout << j.fi << " " << j.se << "\n";
            }
        }
        //cout << res << "\n";
    }


	return res;
}

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