Submission #461225

#	Time	Username	Problem	Language	Result	Execution time	Memory
461225		ymm	Rectangles (IOI19_rect)	C++17	100 / 100	4650 ms	974896 KiB

rect

//
//   I have a dream and a piano
//
 
#include <bits/stdc++.h>
#define FAST ios::sync_with_stdio(0),cin.tie(0)
#define Loop(x,l,r) for(int x=(l);x<(r);++x)
#define LoopR(x,l,r) for(int x=(r)-1;x>=(l);--x)
#define all(v) v.begin(),v.end()
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;
 
const int N = 2520;
int a[N][N];
int b[N][N];
int n, m;
 
short lg[N][N], rg[N][N], dg[N][N], ug[N][N];
short lnl[N][N], rnl[N][N], dnl[N][N], unl[N][N];
short lnlr[N][N], rnlr[N][N], dnlr[N][N], unlr[N][N];
 
template<class Cmp_fn> void mk_nxt(short* di, int* si, int n, Cmp_fn f){
    vector<int> st;
    Loop(i,0,n){
        while(st.size() && !f(si[st.back()], si[i])) st.pop_back();
        di[i] = st.size()? i-st.back(): i+1;
        st.push_back(i);
    }
}
template<class Cmp_fn> void mk_nxt_rv(short* di, int* si, int n, Cmp_fn f){
    vector<int> st;
    LoopR(i,0,n){
        while(st.size() && !f(si[st.back()], si[i])) st.pop_back();
        di[i] = st.size()? st.back()-i: n-i;
        st.push_back(i);
    }
}
 
void init_g_nl()
{
    Loop(i,0,n)
        mk_nxt(lg[i] , a[i], m, greater<int>()),
        mk_nxt(lnl[i], a[i], m, greater_equal<int>()),
        mk_nxt_rv(rg[i] , a[i], m, greater<int>()),
        mk_nxt_rv(rnl[i], a[i], m, greater_equal<int>());
    Loop(j,0,m)
        mk_nxt(ug[j] , b[j], n, greater<int>()),
        mk_nxt(unl[j], b[j], n, greater_equal<int>()),
        mk_nxt_rv(dg[j] , b[j], n, greater<int>()),
        mk_nxt_rv(dnl[j], b[j], n, greater_equal<int>());
    Loop(i,0,n) Loop(j,0,m)
        lnlr[j][i] = lnl[i][j],
        rnlr[j][i] = rnl[i][j],
        unlr[i][j] = unl[j][i],
        dnlr[i][j] = dnl[j][i];
}
 
struct RMQ
{
    int size;
    short a[N<<2];
 
    void init_(short* si, int i, int b, int e)
    {
        if(e-b==1) {a[i] = si[b]; return;}
        init_(si,2*i+1,b,(b+e)/2);
        init_(si,2*i+2,(b+e)/2,e);
        a[i] = min(a[2*i+1], a[2*i+2]);
    }
    short mx;
    bool get_(int l, int r, int i, int b, int e)
    {
        if(a[i] >= mx) return 0;
        if(l <= b && e <= r) return 1;
        if(l < (b+e)/2 && get_(l,r,2*i+1,b,(b+e)/2)) return 1;
        if((b+e)/2 < r && get_(l,r,2*i+2,(b+e)/2,e)) return 1;
        return 0;
    }
 
    void init(short* si, int n){size=n; init_(si,0,0,size);}
    bool get(int l, int r, int target){mx=target;return get_(l,r,0,0,size);}
};
 
RMQ mlnl[N], mrnl[N], mdnl[N], munl[N];
 
void init_rmq(){
    Loop(i,0,m)
        mlnl[i].init(lnlr[i], n),
        mrnl[i].init(rnlr[i], n);
    Loop(i,0,n)
        munl[i].init(unlr[i], m),
        mdnl[i].init(dnlr[i], m);
}
 
typedef tuple<int,int,int,int> tup;
bool good(int i, int j, tup& t)
{
    int l = j-lg[i][j], r = rg[i][j]+j;
    int u = i-ug[j][i], d = dg[j][i]+i;
    t = {l,r,u,d};
    if(l == -1 || r == m || u == -1 || d == n) return 0;
    if(mdnl[u].get(l+1, r, d-u)) return 0;
    if(munl[d].get(l+1, r, d-u)) return 0;
    if(mrnl[l].get(u+1, d, r-l)) return 0;
    if(mlnl[r].get(u+1, d, r-l)) return 0;
    return 1;
}

#pragma GCC optimize("O3")
#pragma GCC target("abm,bmi,bmi2") 
#include <ext/pb_ds/assoc_container.hpp>
struct chash
{
    size_t operator()(ll x) const
    {
        static const size_t FIXED_RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
        size_t ans = x + FIXED_RANDOM;
        ans += 0x786f3d7a52f61cb7;
        ans = (ans ^ (ans >> 27)) * 0x881734ab36fce91b;
        ans = (ans ^ (ans >> 31)) * 0x5256bce6ad237463;
        return ans ^ (ans >> 30);
    }
};
__gnu_pbds::gp_hash_table<ll, __gnu_pbds::null_type, chash> cnted({},{},{},{},{1<<25});
ll tup2qw(tup x){return get<0>(x)+((ll)get<1>(x)<<16)+((ll)get<2>(x)<<32)+((ll)get<3>(x)<<48);}
 
ll count_rectangles(vector<vector<int>> v)
{
    n = v.size(); m = v[0].size();
    Loop(i,0,n) Loop(j,0,m) b[j][i] = a[i][j] = v[i][j];
    init_g_nl();
    init_rmq();
    ll ans = 0;
    Loop(i,0,n) Loop(j,0,m)
    {
        tup t;
        if(good(i,j,t))
        {
            ll qw = tup2qw(t);
            if(cnted.find(qw) != cnted.end()) continue;
            ++ans;
            cnted.insert(qw);
        }
    }
    return ans;
}
 
//int main(){cout << count_rectangles({{4,  8,  7,  5,  6},{7,  4,  10, 3,  5},{9,  7,  20, 14, 2},{9,  14, 7,  3,  6},{5,  7,  5,  2,  7},{4,  5,  13, 5,  6}}) << '\n';}

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