Submission #620033

#	Time	Username	Problem	Language	Result	Execution time	Memory
620033		TimDee	Rectangles (IOI19_rect)	C++17	38 / 100	997 ms	357768 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct segtree {
    
    vector<ll> tree;
    int size;
    int n;
    int neutral;
    
    void put(int i, ll v) {
        
        tree[i]=v;
        
    }
    
    int combine(ll i, ll j) {
        //for min
        //return min(i,j);
        //for max
        return max(i,j);
        //for sum
        //return i+j;
    }
 
    void update(int x, int l, int r, int i) {
        
        if (i>=r || i<l) return;
        if (r-l == 1) return;
        
        int mid=(l+r)/2;
        update(2*x+1,l,mid,i);
        update(2*x+2,mid,r,i);
        
        tree[x]=combine(tree[2*x+1],tree[2*x+2]);
    }
    
    void update(int x, int l, int r) {
 
        if (r-l == 1) return;
        
        int mid=(l+r)/2;
        update(2*x+1,l,mid);
        update(2*x+2,mid,r);
        
        tree[x]=combine(tree[2*x+1],tree[2*x+2]);
    }
    
    segtree(vector<int>&a, int neutr) {
        
        n=a.size();
       
        //for min
        //neutral = inf;
        //for max
        //neutral = -inf;
        //for sum
        //neutral = 0;

        neutral = neutr;

        size=1;
        while (size < n) size*=2;
        
        tree.assign(2*size-1,neutral);
        
        for(int i=0; i<a.size(); ++i) put(size-1+i,a[i]);
        
        update(0,0,size);
        
    }
    
    void clear() {
        
        tree.assign(2*size-1,0);
        
    }
    
    ll calc(int x, int lx, int rx, int l, int r) {
        
        if (lx>=r || rx<=l) return neutral;
        if (lx>=l && rx<=r) return tree[x];
        
        int mid=(lx+rx)/2;
        int a=calc(2*x+1,lx,mid,l,r),
        b=calc(2*x+2,mid,rx,l,r);
        return combine(a,b);
    }
    
    ll query(int l, int r) {
        if (l>=r) return neutral;
        return calc(0,0,size,l,r);
    }
    
    void set(int i, ll v) {
        
        put(size-1+i,v);
        update(0, 0, size, i);
        
    }
    
    void print() {
        
        cout<<"TREE: \n";
        int z=0;
        while (z<tree.size()) {
            for (int i=z; i<2*z+1; i++) cout<<tree[i]<<' ';
            cout<<'\n';
            z=z*2+1;
        }
        cout<<'\n';
        
    }
    
};

int _n, _m;

struct DSU {
 
    vector<int> p;
    vector<int> r;
    vector<int> sz, minr, maxr, minc, maxc, vis;
    
    DSU(int N, int M) {
    	int n=N*M;
        p.assign(n,0);
        r.assign(n,0);
        for (int i=0; i<n; ++i) p[i]=i;
        sz.assign(n,1);
    	minr.assign(n,1);
    	minc.assign(n,1);
    	maxr.assign(n,1);
    	maxc.assign(n,1);
    	vis.assign(n,0);
        for (int i=0; i<n; ++i) {
        	minr[i]=maxr[i]=i/N;
        	minc[i]=maxc[i]=i%M;
        }
    }

    int get(int i) {
           
        return p[i]==i ? i : get(p[i]);
        
    }
    int calc(int i, int j) {
    	int a=i*2500+j;
    	a=get(a);
    	if (vis[a]) return 0;
    	vis[a]=1;
    	//cout<<"component "<<i<<' '<<j<<'\n';
    	//cout<<minr[a]<<' '<<minc[a]<<' '<<maxr[a]<<' '<<maxc[a]<<' '<<sz[a]<<'\n';
    	if (minr[a]==0 || minc[a]==0 || maxc[a]==_m-1 || maxr[a]==_n-1) return 0;
    	return sz[a]==(maxr[a]-minr[a]+1)*(maxc[a]-minc[a]+1);
    }
    
    void uni(int i, int j, int x, int y) {
        	
    	int a=i*2500+j, b=x*2500+y;

        a=get(a);
        b=get(b);
        if (a==b) return;
        
        if (r[a]==r[b]) r[a]++;
        
        if (r[a]<r[b]) {
        	swap(a,b);
        }
        p[b]=a;
        sz[a]+=sz[b];
        minr[a]=min(minr[a],minr[b]);
     	maxr[a]=max(maxr[a],maxr[b]);
     	minc[a]=min(minc[a],minc[b]);
     	maxc[a]=max(maxc[a],maxc[b]);
        
    }
    
};

vector<vector<int>> a;

ll count_rectangles(vector<vector<int>>A) {
	a=A;
	int n=a.size(), m=a[0].size(); 
	_n=n, _m=m;
	if (n<=2 || m<=2) return 0;
	if (n==3) {
		segtree st(a[1],-1);
		ll ans=0;
		vector<int> br(m,0);
		for (int i=1; i<m-1; ++i) {
			br[i] = ( a[1][i]>=a[0][i] || a[1][i]>=a[2][i] );
			//cout<<br[i]<<' ';
		} //cout<<'\n';
		for (int i=1; i<m-1; ++i) {
			for (int j=i; j<m-1; ++j) {
				if (br[j]) break;
				int x=st.query(i,j+1);
				ans += (x<a[1][i-1] && x<a[1][j+1]);
			}
		}
		return ans;
	} 
	int mx=0;
	for (int i=0; i<n; ++i) {
		for (int j=0; j<m; ++j) mx=max(mx,a[i][j]);
	}
	if (mx==0) return 0;
	if (mx==1) {
		DSU dsu(2500,2500);
		vector<vector<int>> vis(n,vector<int>(m,0));
		queue<pair<int,int>> q;
		for (int i=0; i<n; ++i) {
			for (int j=0; j<m; ++j) {
				if (a[i][j]==0) q.push({i,j});
			}
		}
		while (!q.empty()) {
			auto u=q.front(); q.pop();
			int i=u.first, j=u.second;
			//if (vis[i][j]) continue;
			vis[i][j]=1;
			if (i && a[i-1][j]==0) {
				dsu.uni(i,j,i-1,j);
				vis[i-1][j]=1;
			}
			if (i<n-1 && a[i+1][j]==0) {
				dsu.uni(i,j,i+1,j);
				vis[i+1][j]=1;
			}
			if (j && a[i][j-1]==0) {
				dsu.uni(i,j,i,j-1);
				vis[i][j-1]=1;
			}
			if (j<m-1 && a[i][j+1]==0) {
				dsu.uni(i,j,i,j+1);
				vis[i][j+1]=1;
			}
		}
		ll ans=0;
		for (int i=1; i<n-1; ++i) {
			for (int j=1; j<m-1; ++j) {
				if (a[i][j]==0) ans+=dsu.calc(i,j);
			}
		}
		return ans;
	}

	if (n<=80 && m<=80) {

		vector<vector<vector<int>>> row(n,vector<vector<int>>(m,vector<int>(m,0)));
		vector<vector<vector<int>>> col(m,vector<vector<int>>(n,vector<int>(n,0)));
		for (int i=1; i<n-1; ++i) {
			for (int l=1; l<m-1; ++l) {
				for (int r=l; r<m-1; ++r) row[i][l][r]=max(row[i][l][r-1],a[i][r]);
			}
		}
		for (int i=1; i<m-1; ++i) {
			for (int l=1; l<n-1; ++l) {
				for (int r=l; r<n-1; ++r) col[i][l][r]=max(col[i][l][r-1],a[r][i]);
			}
		}

		int ans=0;

		for (int x=1; x<n-1; ++x) {
			for (int y=1; y<m-1; ++y) {
				for (int i=x; i<n-1; ++i) {
					for (int j=y; j<m-1; ++j) {

						int foo=1;
						for (int k=x; k<=i; ++k) foo&=row[k][y][j]<min(a[k][y-1],a[k][j+1]);
						for (int k=y; k<=j; ++k) foo&=col[k][x][i]<min(a[x-1][k],a[i+1][k]);
						ans+=foo;
						//if (foo) cout<<x<<' '<<y<<' '<<i<<' '<<j<<'\n';

					}
				}
			}
		}

		return ans;

	} 

	

		ll ans=0;

		vector<vector<bitset<700>>> row(n,vector<bitset<700>>(m));
		vector<vector<bitset<700>>> col(m,vector<bitset<700>>(n));
		vector<vector<vector<int>>> dp(n,vector<vector<int>>(m,vector<int>(n,0)));
		for (int i=1; i<n-1; ++i) {
			for (int l=1; l<m-1; ++l) {
				mx=0;
				for (int r=l; r<m-1; ++r) {mx=max(mx,a[i][r]); row[i][l][r]=mx<min(a[i][l-1],a[i][r+1]); }
			}
		}
		for (int i=1; i<m-1; ++i) {
			for (int l=1; l<n-1; ++l) {
				mx=0;
				for (int r=l; r<n-1; ++r) {mx=max(mx,a[r][i]); col[i][l][r]=mx<min(a[l-1][i],a[r+1][i]); }
			}
		}

		//for (int x=1; x<n-1; ++x) {
		//	for (int y=1; y<m-1; ++y) {
		//		for (int len=1; y+len<m; ++len) {
		//			for (int i=x; i<n-1; ++i) {
		//				if (row[i][y][y+len-1]) tmp[x][y][len]++;
		//				else break;
		//			}
		//		}
		//	}
		//}
		//tmp.assign(200,vector<vector<int>>(200,vector<int>(200,0)));
		for (int x=1; x<n-1; ++x) {
			for (int y=1; y<m-1; ++y) {
				for (int len=1; x+len<n; ++len) {
					for (int j=y; j<m-1; ++j) {
						if (col[j][x][x+len-1]) dp[x][y][len]++;
						else break;
					}
				}
			}
		}

		for (int x=1; x<n-1; ++x) {
			for (int y=1; y<m-1; ++y) {
				for (int len=1; y+len<m; ++len) {
					for (int i=x; i<n-1; ++i) {
						if (row[i][y][y+len-1]) if (dp[x][y][i-x+1]>=len) ++ans;
						else break;
					}
				}
			}
		}

		/*
				for (int len=1; x+len<n; ++len) {
					for (int j=y; j<m-1; ++j) {
						if (col[j][x][x+len-1]) dp2[x][y][len]++;
						else break;
					}
				}

				for (int len=1; y+len<m; ++len) {
					int k=dp[x][y][len];
					for (int l2=1; l2<=k; ++l2) {
						int p=dp2[x][y][l2];
						if (p>=len) {
							ans++;
							//cout<<x<<' '<<y<<' '<<len<<' '<<k<<' '<<p<<'\n';
						}
					}
				}
			*/
		return ans;
}

Compilation message (stderr)

rect.cpp: In constructor 'segtree::segtree(std::vector<int>&, int)':
rect.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int i=0; i<a.size(); ++i) put(size-1+i,a[i]);
      |                      ~^~~~~~~~~
rect.cpp: In member function 'void segtree::print()':
rect.cpp:108:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         while (z<tree.size()) {
      |                ~^~~~~~~~~~~~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:336:10: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  336 |       if (row[i][y][y+len-1]) if (dp[x][y][i-x+1]>=len) ++ans;
      |          ^

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