Submission #937448

#	Time	Username	Problem	Language	Result	Execution time	Memory
937448		GrindMachine	Rectangles (IOI19_rect)	C++17	100 / 100	2754 ms	660276 KiB

rect

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

read some solutions long back, recollected some ideas from there

look at a given row
how many (i,j) exist s.t i < j and a[i] > a[i+1],a[i+2],...,a[j-1] and a[j] > a[i+1],a[i+2],...,a[j-1]
i.e the ends have stricly larger value than the values in the middle

claim:
the #of such pairs is O(n)

proof:
for simplicity, assume all elems are distinct
we can count such pairs using a stack
maintain a decreasing stack
when pushing index i, pop off all smaller values
(j,i) forms a valid pair, and j is no longer useful (i has bigger value), so it's popped
what about indices in the stack with bigger value?
only 1 such index can form a good pair
15 10 6 5 => assume a[i] = 5, [15,10,6] = contents of stack after popping all guys smaller than 5 (stack contains values for this explanation, not indices)
        ^
(6,5) forms a valid pair
(10,5) does not, because 6 > 5
so only the closest greater to the left of i can form a pair with i (when considering greater elements)
for j to the left of this position, there would exist an index in the middle with value bigger than the right end
so we have proved this by construction

find the valid segments for each row and each col
tot #of valid segments over all rows = O(nm)
tot #of valid segments over all cols = O(nm)

now, fix the lowest horizontal segment of the rectangle
find how far up this horizontal segment can be extended
leftmost vertical segment is also known once the lowest horizontal segment is fixed

vertical segment (k,i) is valid for a given (l,r) if:
k >= horizontal_extend_up-1
vertical_extend_right >= r-1
counting naively is O(nm*max(n,m)) (or something similar), gives 72 points

queries could be answered offline with a fenwick tree for 100 points

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "rect.h"
 
template<typename T>
struct fenwick {
    int siz;
    vector<T> tree;
 
    fenwick() {
 
    }
 
    fenwick(int n) {
        siz = n;
        tree = vector<T>(n + 1);
    }
 
    int lsb(int x) {
        return x & -x;
    }
 
    void build(vector<T> &a, int n) {
        for (int i = 1; i <= n; ++i) {
            int par = i + lsb(i);
            tree[i] += a[i];
 
            if (par <= siz) {
                tree[par] += tree[i];
            }
        }
    }
 
    void pupd(int i, T v) {
        i++;
        while (i <= siz) {
            tree[i] += v;
            i += lsb(i);
        }
    }
 
    T sum(int i) {
        i++;
        T res = 0;
 
        while (i) {
            res += tree[i];
            i -= lsb(i);
        }
 
        return res;
    }
 
    T query(int l, int r) {
        if (l > r) return 0;
        T res = sum(r) - sum(l - 1);
        return res;
    }
};
 
long long count_rectangles(std::vector<std::vector<int> > a) {
    int n = sz(a), m = sz(a[0]);
    if(n <= 2 or m <= 2) return 0;
 
    vector<pii> up[n][m];
    int ptr = 0;
 
    rep(j,m){
        stack<int> st;
        rep(i,n){
            bool eq = false;
            while(!st.empty() and a[i][j] >= a[st.top()][j]){
                int k = st.top();
                st.pop();
                if(a[i][j] == a[k][j]){
                    eq = true;
                }
                if(i-k >= 2){
                    up[i][j].pb({k,ptr++});
                }
            }
 
            if(!st.empty() and !eq){
                int k = st.top();
                if(i-k >= 2){
                    up[i][j].pb({k,ptr++});
                }
            }
 
            st.push(i);
        }
    }
 
    vector<int> farthest(ptr);
    int seg_ptr[n][n];
    memset(seg_ptr,-1,sizeof seg_ptr);

    rev(j,m-1,0){
        if(j+2 < m){
            rep(i,n){
                for(auto [k,ptr] : up[i][j+2]){
                    seg_ptr[k][i] = -1;
                }
            }   
        }

        if(j+1 < m){
            rep(i,n){
                for(auto [k,ptr] : up[i][j+1]){
                    seg_ptr[k][i] = ptr;
                }
            }   
        }

        rep(i,n){
            for(auto [k,ptr] : up[i][j]){
                if(seg_ptr[k][i] != -1){
                    farthest[ptr] = farthest[seg_ptr[k][i]];
                }
                else{
                    farthest[ptr] = j;
                }
            }
        }
    }
 
    int prev_occ[m][m], first_occ[m][m];
    memset(prev_occ,-1,sizeof prev_occ);
    memset(first_occ,-1,sizeof first_occ);
 
    ll ans = 0;
    vector<int> queries[ptr];
 
    rep1(i,n-2){
        stack<int> st;
        vector<pii> good;
        rep(j,m){
            bool eq = false;
            while(!st.empty() and a[i][j] >= a[i][st.top()]){
                int k = st.top();
                st.pop();
                if(a[i][j] == a[i][k]){
                    eq = true;
                }
                if(j-k >= 2){
                    good.pb({k,j});
                }
            }
 
            // cout << j << endl;
            // cout << eq << endl;
            // auto st_copy = st;
            // while(!st_copy.empty()){
            //  cout << st_copy.top() << " ";
            //  st_copy.pop();
            // }
            // cout << endl;
 
            if(!st.empty() and !eq){
                int k = st.top();
                if(j-k >= 2){
                    // cout << k << " " << j << endl;
                    good.pb({k,j});
                }
            }
 
            st.push(j);
        }
 
        for(auto [l,r] : good){
            if(prev_occ[l][r] != i-1){
                first_occ[l][r] = i;
            }
 
            prev_occ[l][r] = i;
 
            int lo = 0, hi = sz(up[i+1][l+1])-1;
            int pos = -1;
 
            while(lo <= hi){
                int mid = (lo+hi) >> 1;
                if(up[i+1][l+1][mid].ff >= first_occ[l][r]-1){
                    pos = mid;
                    lo = mid+1;
                }
                else{
                    hi = mid-1;
                }
            }
 
            if(pos != -1){
                int ind = up[i+1][l+1][pos].ss;
                queries[ind].pb(r);
            }
 
            /*
 
            for(auto [k,ptr] : up[i+1][l+1]){
                if(k >= first_occ[l][r]-1){
                    if(farthest[ptr] >= r-1){
                        ans++;
                    }
                }
                else{
                    break;
                }
            }
 
            */
        }
    }
 
    fenwick<int> fenw(m);
 
    rep(i,n){
        rep(j,m){
            for(auto [k,ptr] : up[i][j]){
                fenw.pupd(farthest[ptr],1);
                trav(r,queries[ptr]){
                    ans += fenw.query(r-1,m-1);
                }
            }
 
            for(auto [k,ptr] : up[i][j]){
                fenw.pupd(farthest[ptr],-1);
            }
        }
    }
 
    /*
 
    int oans = 0;
 
    rep1(i1,n-2){
        rep1(j1,m-2){
            for(int i2 = i1; i2 < n-1; ++i2){
                for(int j2 = j1; j2 < m-1; ++j2){
                    bool ok = true;
                    for(int r = i1; r <= i2; ++r){
                        for(int c = j1; c <= j2; ++c){
                            if(a[r][c] >= min({a[i1-1][c],a[i2+1][c],a[r][j1-1],a[r][j2+1]})){
                                ok = false;
                                break;
                            }
                        }
                        if(!ok) break;
                    }
 
                    if(ok){
                        oans++;
                        cout << i1 << " " << j1 << " " << i2 << " " << j2 << endl;
                    }
                }
            }
        }
    }
    
    */
    
    // cout << ans << endl;
    // cout << oans << endl;
    // cout << endl;
 
    // assert(ans == oans);
 
    return ans;
}

• 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