Submission #371625

#	Time	Username	Problem	Language	Result	Execution time	Memory
371625		jainbot27	Rectangles (IOI19_rect)	C++17	72 / 100	5132 ms	662672 KiB

rect

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

ll count_rectangles(vector<vi> a){
    int n = siz(a), m = siz(a[0]); ll ans = 0;
    auto precalc = [&](vector<vi> b){
        int N = siz(b), M = siz(b[0]);
        auto go = [&](vi v){
            stack<pii> s;
            vi res(M);
            F0R(i, M){
                while(siz(s)&&s.top().f<v[i]){
                    s.pop();
                }
                if(!siz(s)) res[i]=-1;
                else res[i]=s.top().s;
                s.push({v[i], i});
            }
            return res;
        };
        vector<vector<vpii>> res(N, vector<vpii>(M));
        F0R(i, N){
            vi l = go(b[i]);
            reverse(all(b[i]));
            vi r = go(b[i]);
            reverse(all(b[i]));
            reverse(all(r));
            F0R(j, M){
                if(r[j]!=-1) r[j]=M-1-r[j];
            }
            F0R(j, M){
                if(l[j]!=-1&&l[j]!=j-1){
                    res[i][j-1].pb({l[j]+1, 1});
                }
            }
            F0R(j, M){
                if(r[j]!=-1&&r[j]!=j+1){
                    res[i][r[j]-1].pb({j+1, 1});
                }
            }
            F0R(j, M){
                sort(all(res[i][j]));
                res[i][j].resize(unique(all(res[i][j]))-res[i][j].begin());
            }
        }
        F0R(i, N-1){
            F0R(j, M){
                trav(x, res[i][j]){
                    trav(y, res[i+1][j]){
                        if(x.f==y.f){
                            y.s = x.s+1;
                        }
                    }
                }
            }
        }
        return res;
    };
    vector<vector<vpii>> x = precalc(a);
    vector<vi> c(m, vi(n));
    F0R(i, n)
        F0R(j, m)
            c[j][i]=a[i][j];
    vector<vector<vpii>> y2 = precalc(c);
    vector<vector<vpii>> y(n, vector<vpii>(m));
    F0R(i, n)
        F0R(j, m)
            y[i][j]=y2[j][i];
    F0R(i, n){
        F0R(j, m){
            trav(v, x[i][j]){
                trav(v2, y[i][j]){
                    if(v.s>=i-v2.f+1&&v2.s>=j-v.f+1) {
                        ans++;
                    }
                }
            }
        }
    }
    return ans;
}

//int32_t main(){
//    ios_base::sync_with_stdio(0); cin.tie(0);
//    int N, M; cin >> N >> M;
//    vector<vi> inp(N, vi(M));
//    F0R(i, N){
//        F0R(j, M){
//            cin >> inp[i][j];
//        }
//    }
//    cout << count_rectangles(inp) << nl;

//    return 0;
//}

• 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: 0 / 28