Submission #772769

#	Time	Username	Problem	Language	Result	Execution time	Memory
772769		I_Love_EliskaM_	Rectangles (IOI19_rect)	C++14	72 / 100	3201 ms	384172 KiB

rect

    #include "rect.h"
    #pragma GCC optimize("O3","unroll-loops")
    #pragma GCC target("avx2,popcnt")
    #include <bits/stdc++.h>
    using namespace std;
    #define forn(i,n) for(int i=0; i<n; ++i)
    #define pi pair<int,int>
    #define f first
    #define s second
    #define ll long long
    #define pb push_back
    #define all(x) x.begin(),x.end()
     
     
    struct DSU {
    	vector<int> p, sz, l, r, t, d;
    	int m;
    	DSU(int n, int _m) {
    		m=_m;
    		forn(i,n*m) {
    			p.pb(i);
    			sz.pb(1);
    			l.pb(i%m);
    			r.pb(i%m);
    			t.pb(i/m);
    			d.pb(i/m);
    		}
    	}
    	int get(int u) {
    		return p[u]==u?u:get(p[u]);
    	}
    	void uni(int u, int v) {
    		u=get(u), v=get(v);
    		if (u==v) return;
    		if (sz[u]<sz[v]) swap(u,v);
    		p[v]=u;
    		sz[u]+=sz[v];
    		l[u]=min(l[u],l[v]);
    		r[u]=max(r[u],r[v]);
    		t[u]=min(t[u],t[v]);
    		d[u]=max(d[u],d[v]);
    	}
    	void uni(int a, int b, int c, int d) {
    		uni(a*m+b,c*m+d);
    	}
    };
    ll wrong(vector<vector<int>> b) {
    	int n=b.size(), m=b[0].size();
    	vector<vector<int>> a(n+2,vector<int>(m+2,-1));
    	forn(i,n) forn(j,m) a[i+1][j+1]=b[i][j];
    	vector<pi> v;
    	n+=2, m+=2;
    	DSU dsu(n,m);
    	forn(i,n) forn(j,m) if (a[i][j]!=-1) v.pb({a[i][j],i*m+j});
    	sort(all(v));
     
    	vector<vector<int>> ok(n,vector<int>(m,0));
    	forn(i,n) forn(j,m) {
    		if (i==0 || i==n-1) ok[i][j]=1;
    		if (j==0 || j==m-1) ok[i][j]=1;
    	}
    	forn(i,n) forn(j,m) if (ok[i][j]) dsu.uni(i,j,0,0);
     
    	ll ans=0;
    	int N=v.size();
    	for(int i=0; i<N; ) {
    		vector<int> z;
    		int x=v[i].f;
    		while (i<N && v[i].f==x) {
    			z.pb(v[i].s);
    			++i;
    		}
    		for(auto&it:z) {
    			int x=it/m, y=it%m;
    			if (ok[x-1][y]) dsu.uni(x-1,y,x,y);
    			if (ok[x+1][y]) dsu.uni(x+1,y,x,y);
    			if (ok[x][y-1]) dsu.uni(x,y-1,x,y);
    			if (ok[x][y+1]) dsu.uni(x,y+1,x,y);
    			ok[x][y]=1;
    		}
    		map<int,int> was;
    		for(auto&it:z) {
    			int x=it/m, y=it%m; 
     
    			int u=dsu.get(it);
    			if (was[u]) continue;
    			was[u]=1;
    			int b=dsu.l[u];
    			int a=dsu.t[u];
    			int d=dsu.r[u];
    			int c=dsu.d[u];
    			int k=(c-a+1)*(d-b+1);
    			if (k==dsu.sz[u]) ++ans;
    		}
    	}
    	return ans-1;
    }
     
     
    const int N=700;
    struct dsu {
    	vector<int> p,sz,l,r;
    	dsu(int n) {
    		forn(i,n) p.pb(i), sz.pb(1);
    		l=r=p;
    	}
    	int get(int u) {
    		return p[u]==u?u:get(p[u]);
    	}
    	void uni(int u, int v) {
    		u=get(u),v=get(v);
    		if (u==v) return;
    		if (sz[u]<sz[v]) swap(u,v);
    		p[v]=u;
    		sz[u]+=sz[v];
    		l[u]=min(l[u],l[v]);
    		r[u]=max(r[u],r[v]);
    	}
    };
    vector<dsu> dsu1(N,dsu(N)), dsu2(N,dsu(N));
    int ok[N][N];
    int a[N][N];
    bitset<N> dp1[N][N], dp2[N][N];
     
    ll count_rectangles(vector<vector<int>> b) {
     
    	int n=b.size(), m=b[0].size();
    	if (min(n,m)<3) return 0;
    	int mx=0; for(auto&x:b) for(auto&y:x) mx=max(mx,y);
    	if (mx==1) return wrong(b);
     
    	if (n==3) {
    		ll ans=0;
    		for (int i=0; i<m; ++i) {
    			int mx=0;
    			for (int j=i+1; j<m-1; ++j) {
    				if (b[0][j]<=b[1][j] || b[1][j]>=b[2][j]) break;
    				mx=max(mx,b[1][j]);
    				ans += b[1][i]>mx && mx<b[1][j+1];
    			}
    		}
    		return ans;
    	}
    	if (max(n,m)>N) exit(0);
    	forn(i,n) forn(j,m) a[i][j]=b[i][j];
     
    	forn(i,n) {
    		for (int l=0; l<m; ++l) {
    			int mx=0;
    			for (int r=l+1; r+1<m; ++r) {
    				mx=max(mx,a[i][r]);
    				dp1[l+1][r][i]=a[i][l]>mx && mx<a[i][r+1];
    			}
    		}
    	}
    	forn(i,m) {
    		for (int l=0; l<n; ++l) {
    			int mx=0;
    			for (int r=l+1; r+1<n; ++r) {
    				mx=max(mx,a[r][i]);
    				dp2[l+1][r][i]=a[l][i]>mx && mx<a[r+1][i];
    			}
    		}
    	}
     
    	vector<pi> v;
    	forn(i,n) forn(j,m) v.pb({a[i][j],i*m+j});
    	sort(all(v));
     
    	ll ans=0;
    	int N=v.size();
    	map<ll,ll> was;
    	for(int i=0; i<N; ) {
    		vector<int> z;
    		int x=v[i].f;
    		while (i<N && v[i].f==x) {
    			z.pb(v[i].s);
    			++i;
    		}
    		for(auto&it:z) {
    			int x=it/m, y=it%m;
    			if (x) if (ok[x-1][y]) dsu1[y].uni(x-1,x); 
    			if (x<n-1) if (ok[x+1][y]) dsu1[y].uni(x+1,x);
    			if (y) if (ok[x][y-1]) dsu2[x].uni(y-1,y);
    			if (y<m-1) if (ok[x][y+1]) dsu2[x].uni(y+1,y);
    			ok[x][y]=1;
    		}
    		for(auto&it:z) {
    			int x=it/m, y=it%m;
    			int u=dsu1[y].get(x);
    			int a=dsu1[y].l[u], c=dsu1[y].r[u];
    			int v=dsu2[x].get(y);
    			int b=dsu2[x].l[v], d=dsu2[x].r[v];
    			if (a==0 || b==0 || c==n-1 || d==m-1) continue;
    			if (was[a*m+b+n*m*(c*m+d)]) continue;
    			was[a*m+b+n*m*(c*m+d)]=1;
    			int ok=1;
    			for (int i=a; i<=c; ++i) {
    				ok&=dp1[b][d][i];
    			}
    			for (int i=b; i<=d; ++i) {
    				ok&=dp2[a][c][i];
    			}
    			ans+=ok;
    		}
    	}
    	return ans;
    }

Compilation message (stderr)

rect.cpp: In function 'long long int wrong(std::vector<std::vector<int> >)':
rect.cpp:83:12: warning: unused variable 'x' [-Wunused-variable]
   83 |        int x=it/m, y=it%m;
      |            ^
rect.cpp:83:20: warning: unused variable 'y' [-Wunused-variable]
   83 |        int x=it/m, y=it%m;
      |                    ^

• 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