Submission #372352

#	Time	Username	Problem	Language	Result	Execution time	Memory
372352		jainbot27	Rectangles (IOI19_rect)	C++17	59 / 100	1460 ms	1048580 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<map<int, int>>> res(N, vector<map<int, int>>(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});
                    res[i][j-1][l[j]+1]=1;
                }
            }
            F0R(j, M){
                if(r[j]!=-1&&r[j]!=j+1){
                    //res[i][r[j]-1].pb({j+1, 1});
                    res[i][r[j]-1][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]){
                    if(res[i+1][j].count(x.f)){
                        res[i+1][j][x.f]=x.s+1;
                    }
                }
            }
        }
        return res;
    };
    vector<vector<map<int, int>>> X = precalc(a);
    vector<vi> c(m, vi(n));
    F0R(i, n)
        F0R(j, m)
            c[j][i]=a[i][j];
    vector<vector<map<int, int>>> Y2 = precalc(c);
    vector<vector<map<int, int>>> Y(n, vector<map<int, int>>(m));
    F0R(i, n)
        F0R(j, m)
            Y[i][j]=Y2[j][i];
    vector<vector<vpii>> x, y;
    x = y = vector<vector<vpii>>(n, vector<vpii>(m));
    F0R(i, n){
        F0R(j, m){
            for(auto Q : X[i][j]){
                pair<int, int> V = Q;
                x[i][j].pb(V);
            }
            for(auto Q : Y[i][j]){
                pair<int, int> V = Q;
                y[i][j].pb(V);
            }
        }
    }
    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: 0 / 13
• Subtask 7: 0 / 28