Submission #154452

#	Time	Username	Problem	Language	Result	Execution time	Memory
154452		crackersamdjam	Rectangles (IOI19_rect)	C++14	23 / 100	1645 ms	445308 KiB

rect

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

#include <bits/stdc++.h>
const int MM = 2502;

#ifndef ONLINE_JUDGE
#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...);}
#endif

int n, m, ans, stl, vecl;
int first[MM], last[MM], bit[MM];
std::pair<int, int> st[MM], vec[MM];
std::vector<std::pair<int, int>> hor[MM][MM], vert[MM][MM];

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

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

long long count_rectangles(std::vector<std::vector<int>> a){
    n = a.size(), m = a[0].size();
    
    for(int i = 0; i < n; i++){
        stl = 0;
        for(int j = 0; j < m; j++){
            //remove duplicates
            while(stl && st[stl].first < a[i][j])
                stl--;
            first[j] = (!stl || st[stl].first == a[i][j]) ? -1 : st[stl].second;
            st[++stl] = {a[i][j], j};
        }
        stl = 0;
        for(int j = m-1; j >= 0; j--){
            while(stl && st[stl].first <= a[i][j])
                stl--;
            last[j] = !stl ? -1 : st[stl].second;
            st[++stl] = {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]].push_back({last[j], 1});
        }
    }
    
    for(int j = 0; j < m; j++){
        stl = 0;
        for(int i = 0; i < n; i++){
            //remove duplicates
            while(stl && st[stl].first < a[i][j])
                stl--;
            first[i] = (!stl || st[stl].first == a[i][j]) ? -1 : st[stl].second;
            st[++stl] = {a[i][j], i};
        }
        stl = 0;
        for(int i = n-1; i >= 0; i--){
            while(stl && st[stl].first <= a[i][j])
                stl--;
            last[i] = !stl ? -1 : st[stl].second;
            st[++stl] = {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].push_back({last[i], 1});
        }
    }
    
    for(int i = n-1; i >= 0; i--){
        for(int j = m-1; j >= 0; j--){
            
            assert(std::is_sorted(hor[i][j].begin(), hor[i][j].end()));
            assert(std::is_sorted(vert[i][j].begin(), vert[i][j].end()));
            
            //sort(hor[i][j].begin(), hor[i][j].end());
            //sort(vert[i][j].begin(), vert[i][j].end());
            //shouldn't be necessary
            
            /*
    for(int i=0;i<m;i++){
		for(int j=n-2;j>=0;j--){
			int l=0,r=0;
			while(l<rowranges[j][i].size()&&r<rowranges[j+1][i].size()){
				if(rowranges[j][i][l].first==rowranges[j+1][i][r].first){
					rowranges[j][i][l].second+=rowranges[j+1][i][r].second;
					l++;
				}
				else if(rowranges[j][i][l].first>rowranges[j+1][i][r].first){
					r++;
				}
				else l++;
			}
		}
	}
             */
            int l = 0, r = 0;
            
            while(l < vert[i][j].size() && r < vert[i][j+1].size()){
                if(vert[i][j][l].first == vert[i][j+1][r].first){
                    vert[i][j][l].second = vert[i][j+1][r].second+1;
                    l++;
                }
                else if(vert[i][j][l].first > vert[i][j+1][r].first)
                    r++;
                else
                    l++;
            }
            
            l = r = 0;
    
            while(l < hor[i][j].size() && r < hor[i+1][j].size()){
                if(hor[i][j][l].first == hor[i+1][j][r].first){
                    hor[i][j][l].second = hor[i+1][j][r].second+1;
                    l++;
                }
                else if(hor[i][j][l].first > hor[i+1][j][r].first)
                    r++;
                else
                    l++;
            }
            /*
             * //should be hor, but not using anyway
            for(int k = 0; k < vert[i][j].size(); k++)
                vec[k] = vert[i][j][k];
            vecl = vert[i][j].size();
             */
            /*
            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]){
                if(hor[i+1][j].count(x.first))
                    x.second += hor[i+1][j][x.first];
                vec[vecl++] = {x.first-j+1, x.second};
            }
             */
            /*
            sort(vec, vec+vecl, [](const std::pair<int, int> &x, const std::pair<int, int> &y){
                return x.second > y.second;
            });
            */
            l = hor[i][j].size()-1;
            
            //printf("Start "); print(i, j);
            
            for(int k = vert[i][j].size()-1; k >= 0; k--){
                auto &b = vert[i][j][k];
                //printf("b "); print(b.first, b.second);
                while(l >= 0 && b.first-i+1 <= hor[i][j][l].second){
                    //printf("a "); print(hor[i][j][l].first, hor[i][j][l].second);
                    update(hor[i][j][l--].first-j+1, 1);
                }
                ans += query(b.second);
            }
            
            l++;
            while(l < hor[i][j].size())
                update(hor[i][j][l++].first-j+1, -1);
            
            //adjust
            
            //vecl = 0;
        }
    }
    
    return ans;
}

#ifndef ONLINE_JUDGE
int notmain(){
    
    printf("%lld\n", 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

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:119:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(l < vert[i][j].size() && r < vert[i][j+1].size()){
                   ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:119:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(l < vert[i][j].size() && r < vert[i][j+1].size()){
                                            ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:132:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(l < hor[i][j].size() && r < hor[i+1][j].size()){
                   ~~^~~~~~~~~~~~~~~~~~
rect.cpp:132:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(l < hor[i][j].size() && r < hor[i+1][j].size()){
                                           ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:179:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(l < hor[i][j].size())
                   ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28