제출 #371620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371620		jainbot27	Rectangles (IOI19_rect)	C++17	72 / 100	5109 ms	673380 KiB

rect

#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]);
        //F0R(i, N){
        //    F0R(j, M){
        //        cout << b[i][j] << ' ';
        //    }
        //    cout << nl;
        //}
        auto go = [&](vi v){
            stack<pii> s;
            vi res(M);
            F0R(i, M){
                while(siz(s)&&s.top().f<v[i]){
                    //cout << s.top().f << ' ' << v[i] << nl;
                    s.pop();
                }
                if(!siz(s)) res[i]=-1;
                else res[i]=s.top().s;
                //cout << res[i] << ' ';
                s.push({v[i], i});
            }
            //cout << nl;
            return res;
        };
        vector<vector<vpii>> res(N, vector<vpii>(M));
        F0R(i, N){
            //F0R(j, M) cout << b[i][j] << ' ';
            //cout << nl;
            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];
                //cout << r[j] << ' ';
            }
            //cout << nl;
            F0R(j, M){
                //cout << l[j] << ' ';
                if(l[j]!=-1&&l[j]!=j-1){
                    assert(l[j]<=j);
                    res[i][j-1].pb({l[j]+1, 1});
                }
            }
            //cout << nl << nl;
            F0R(j, M){
                if(r[j]!=-1&&r[j]!=j+1){
                    assert(r[j]>=j);
                    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(X, x[i][j]){
    //            cout << i << ' ' << j << ' ' <<  X.f << ' ' << X.s << nl;
    //        }
    //    }
    //} 
    //cout << nl;
    //F0R(i, n){
    //    F0R(j, m){
    //        trav(X, y[i][j]){
    //            cout << i << ' ' << j << ' ' << X.f << ' ' << X.s << nl;
    //        }
    //    }
    //}
    //cout << nl;
    F0R(i, n){
        F0R(j, m){
            trav(v, x[i][j]){
                //cout << "V: " << v.f << ' ' << v.s << nl;
                trav(v2, y[i][j]){
                        //cout << i << ' ' << j << ' ' << v.f << ' ' << v.s << ' ' << v2.f << ' ' << v2.s << nl;
                    if(v.s>=i-v2.f+1&&v2.s>=j-v.f+1) {
                        ans++;
                    }
                }
            }
            //trav(v2, y[i][j]){
            //    cout << "V2: " << v2.f << ' ' << v2.s << nl;
            //}
        }
    }
    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