Submission #154447

#	Time	Username	Problem	Language	Result	Execution time	Memory
154447		crackersamdjam	Rectangles (IOI19_rect)	C++14	72 / 100	3227 ms	1048580 KiB

rect

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4,popcnt,abm,mmx,tune=native")

#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

using namespace std;
const int MM = 2505;

int n, m, ans;

int first[MM], last[MM], bit[MM];
stack<pair<int, int>> st;

map<int, int, greater<int>> hor[MM][MM], vert[MM][MM];
//stores either right or down endpoint, and "dp" val

void update(int i, int v){
    for(; i < MM; i += i&-i)
        bit[i] += v;
}

int query(int i){
    int ret = 0;
    for(; i; i -= i&-i)
        ret += bit[i];
    return ret;
}

void clear(){
    while(!st.empty())
        st.pop();
}

vector<pair<int, int>> vec;

long long count_rectangles(vector<vector<int>> a){
    n = a.size(), m = a[0].size();
    
    for(int i = 0; i < n; i++){
        clear();
        for(int j = 0; j < m; j++){
            //remove duplicates
            while(!st.empty() && st.top().first < a[i][j])
                st.pop();
            first[j] = (st.empty() || st.top().first == a[i][j]) ? -1 : st.top().second;
            st.push({a[i][j], j});
        }
        clear();
        for(int j = m-1; j >= 0; j--){
            while(!st.empty() && st.top().first <= a[i][j])
                st.pop();
            last[j] = st.empty() ? -1 : st.top().second;
            st.push({a[i][j], j});
        }
        for(int j = 0; j < m; j++){
            if(first[j] == -1 || last[j] == -1)
                continue;
            
            first[j]++, last[j]--;
            
            hor[i][first[j]][last[j]] = 1;
        }
    }
    
    for(int j = 0; j < m; j++){
        clear();
        for(int i = 0; i < n; i++){
            //remove duplicates
            while(!st.empty() && st.top().first < a[i][j])
                st.pop();
            first[i] = (st.empty() || st.top().first == a[i][j]) ? -1 : st.top().second;
            st.push({a[i][j], i});
        }
        clear();
        for(int i = n-1; i >= 0; i--){
            while(!st.empty() && st.top().first <= a[i][j])
                st.pop();
            last[i] = st.empty() ? -1 : st.top().second;
            st.push({a[i][j], i});
        }
        for(int i = 0; i < n; i++){
            if(first[i] == -1 || last[i] == -1)
                continue;
            
            first[i]++, last[i]--;
            
            vert[first[i]][j][last[i]] = 1;
        }
    }
    
    for(int i = n-1; i >= 0; i--){
        for(int j = m-1; j >= 0; j--){
            for(auto &x: hor[i][j])
                if(hor[i+1][j].count(x.first))
                    x.second += hor[i+1][j][x.first];
    
            for(auto &x: vert[i][j])
                if(vert[i][j+1].count(x.first))
                    x.second += vert[i][j+1][x.first];
                
            for(auto &x: hor[i][j])
                vec.push_back({x.first-j+1, x.second}); //adjust
            sort(vec.begin(), vec.end(), [](auto &x, auto &y){
                return x.second > y.second;
            });
            
            int l = 0;
            
            for(auto &b: vert[i][j]){
                int bf = b.first-i+1;
                
                while(l < vec.size() && bf <= vec[l].second)
                    update(vec[l++].first, 1);
                ans += query(b.second);
            }
            
            while(l)
                update(vec[--l].first, -1);
    
            vec.clear();
        }
    }
    
    return ans;
}
/*
#ifndef ONLINE_JUDGE
int main(){
    
    print(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}})
    );
    
    return 0;
}
#endif
 */
/*
 * in a row, for every point, get 1st left > and 1st right greater
 * this will get all possible
 *
 * using mono stack
 *
 *
 * sort row segments
 * starting at point i, on row j
 * for each (i, r), dp for how long can go down
 *
 * then do same for vertical
 *
 * when it works is when: vert_seg <= dp_vert[hor_seg] and hor_seg <= dp_hor[vert_seg]
 *
 * sort hor and vert by y reversed
 * loop through vert with l ptr for hor
 *      while hor[l] >= y, push hor[l++].x into bit
 *      answer += query_greater_than_equals(vert[i].x)
 *
 * vertical <= NM
 * horizontal <= NM
 * time complexity vert * log(hor) = NM log(NM)
 */

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:120:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(l < vec.size() && bf <= vec[l].second)
                       ~~^~~~~~~~~~~~

• 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