oj.uz

Submission #772769

# Submission time Handle Problem Language Result Execution time Memory
772769 2023-07-04T11:06:25 Z I_Love_EliskaM_ Rectangles (IOI19_rect) C++14
72 / 100
 3201 ms 384172 KB 
    #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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15956 KB Output is correct
2 Correct 9 ms 16400 KB Output is correct
3 Correct 10 ms 16336 KB Output is correct
4 Correct 9 ms 16340 KB Output is correct
5 Correct 9 ms 16340 KB Output is correct
6 Correct 9 ms 16340 KB Output is correct
7 Correct 11 ms 16268 KB Output is correct
8 Correct 9 ms 16076 KB Output is correct
9 Correct 9 ms 16340 KB Output is correct
10 Correct 9 ms 16400 KB Output is correct
11 Correct 9 ms 16320 KB Output is correct
12 Correct 9 ms 16340 KB Output is correct
13 Correct 10 ms 15888 KB Output is correct
14 Correct 9 ms 15888 KB Output is correct
15 Correct 8 ms 15956 KB Output is correct
16 Correct 8 ms 15872 KB Output is correct
17 Correct 10 ms 15888 KB Output is correct
18 Correct 9 ms 15832 KB Output is correct
19 Correct 9 ms 15828 KB Output is correct
20 Correct 10 ms 15848 KB Output is correct
21 Correct 9 ms 15884 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15956 KB Output is correct
2 Correct 9 ms 16400 KB Output is correct
3 Correct 10 ms 16336 KB Output is correct
4 Correct 9 ms 16340 KB Output is correct
5 Correct 9 ms 16340 KB Output is correct
6 Correct 9 ms 16340 KB Output is correct
7 Correct 11 ms 16268 KB Output is correct
8 Correct 9 ms 16076 KB Output is correct
9 Correct 9 ms 16340 KB Output is correct
10 Correct 9 ms 16400 KB Output is correct
11 Correct 9 ms 16320 KB Output is correct
12 Correct 9 ms 16340 KB Output is correct
13 Correct 10 ms 15888 KB Output is correct
14 Correct 9 ms 15888 KB Output is correct
15 Correct 8 ms 15956 KB Output is correct
16 Correct 8 ms 15872 KB Output is correct
17 Correct 10 ms 15888 KB Output is correct
18 Correct 9 ms 15832 KB Output is correct
19 Correct 9 ms 15828 KB Output is correct
20 Correct 10 ms 15848 KB Output is correct
21 Correct 9 ms 15884 KB Output is correct
22 Correct 18 ms 17944 KB Output is correct
23 Correct 15 ms 17948 KB Output is correct
24 Correct 15 ms 17948 KB Output is correct
25 Correct 14 ms 17744 KB Output is correct
26 Correct 15 ms 17876 KB Output is correct
27 Correct 14 ms 17848 KB Output is correct
28 Correct 15 ms 17832 KB Output is correct
29 Correct 12 ms 17228 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15956 KB Output is correct
2 Correct 9 ms 16400 KB Output is correct
3 Correct 10 ms 16336 KB Output is correct
4 Correct 9 ms 16340 KB Output is correct
5 Correct 9 ms 16340 KB Output is correct
6 Correct 9 ms 16340 KB Output is correct
7 Correct 11 ms 16268 KB Output is correct
8 Correct 9 ms 16076 KB Output is correct
9 Correct 9 ms 16340 KB Output is correct
10 Correct 9 ms 16400 KB Output is correct
11 Correct 9 ms 16320 KB Output is correct
12 Correct 9 ms 16340 KB Output is correct
13 Correct 10 ms 15888 KB Output is correct
14 Correct 9 ms 15888 KB Output is correct
15 Correct 8 ms 15956 KB Output is correct
16 Correct 8 ms 15872 KB Output is correct
17 Correct 18 ms 17944 KB Output is correct
18 Correct 15 ms 17948 KB Output is correct
19 Correct 15 ms 17948 KB Output is correct
20 Correct 14 ms 17744 KB Output is correct
21 Correct 15 ms 17876 KB Output is correct
22 Correct 14 ms 17848 KB Output is correct
23 Correct 15 ms 17832 KB Output is correct
24 Correct 12 ms 17228 KB Output is correct
25 Correct 10 ms 15888 KB Output is correct
26 Correct 9 ms 15832 KB Output is correct
27 Correct 9 ms 15828 KB Output is correct
28 Correct 10 ms 15848 KB Output is correct
29 Correct 9 ms 15884 KB Output is correct
30 Correct 79 ms 25240 KB Output is correct
31 Correct 76 ms 25288 KB Output is correct
32 Correct 78 ms 25300 KB Output is correct
33 Correct 60 ms 24068 KB Output is correct
34 Correct 71 ms 24940 KB Output is correct
35 Correct 71 ms 25080 KB Output is correct
36 Correct 69 ms 24736 KB Output is correct
37 Correct 71 ms 24732 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15956 KB Output is correct
2 Correct 9 ms 16400 KB Output is correct
3 Correct 10 ms 16336 KB Output is correct
4 Correct 9 ms 16340 KB Output is correct
5 Correct 9 ms 16340 KB Output is correct
6 Correct 9 ms 16340 KB Output is correct
7 Correct 11 ms 16268 KB Output is correct
8 Correct 9 ms 16076 KB Output is correct
9 Correct 9 ms 16340 KB Output is correct
10 Correct 9 ms 16400 KB Output is correct
11 Correct 9 ms 16320 KB Output is correct
12 Correct 9 ms 16340 KB Output is correct
13 Correct 10 ms 15888 KB Output is correct
14 Correct 9 ms 15888 KB Output is correct
15 Correct 8 ms 15956 KB Output is correct
16 Correct 8 ms 15872 KB Output is correct
17 Correct 18 ms 17944 KB Output is correct
18 Correct 15 ms 17948 KB Output is correct
19 Correct 15 ms 17948 KB Output is correct
20 Correct 14 ms 17744 KB Output is correct
21 Correct 15 ms 17876 KB Output is correct
22 Correct 14 ms 17848 KB Output is correct
23 Correct 15 ms 17832 KB Output is correct
24 Correct 12 ms 17228 KB Output is correct
25 Correct 79 ms 25240 KB Output is correct
26 Correct 76 ms 25288 KB Output is correct
27 Correct 78 ms 25300 KB Output is correct
28 Correct 60 ms 24068 KB Output is correct
29 Correct 71 ms 24940 KB Output is correct
30 Correct 71 ms 25080 KB Output is correct
31 Correct 69 ms 24736 KB Output is correct
32 Correct 71 ms 24732 KB Output is correct
33 Correct 10 ms 15888 KB Output is correct
34 Correct 9 ms 15832 KB Output is correct
35 Correct 9 ms 15828 KB Output is correct
36 Correct 10 ms 15848 KB Output is correct
37 Correct 9 ms 15884 KB Output is correct
38 Correct 2434 ms 77252 KB Output is correct
39 Correct 2529 ms 77364 KB Output is correct
40 Correct 2527 ms 77248 KB Output is correct
41 Correct 2474 ms 77244 KB Output is correct
42 Correct 3092 ms 107712 KB Output is correct
43 Correct 3120 ms 107628 KB Output is correct
44 Correct 3201 ms 107636 KB Output is correct
45 Correct 2847 ms 102164 KB Output is correct
46 Correct 109 ms 44476 KB Output is correct
47 Correct 2622 ms 94780 KB Output is correct
48 Correct 3076 ms 106280 KB Output is correct
49 Correct 3146 ms 106752 KB Output is correct
50 Correct 1168 ms 70492 KB Output is correct
51 Correct 1090 ms 68448 KB Output is correct
52 Correct 2853 ms 101520 KB Output is correct
53 Correct 3084 ms 101896 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15868 KB Output is correct
2 Correct 19 ms 15976 KB Output is correct
3 Correct 8 ms 15828 KB Output is correct
4 Correct 9 ms 15880 KB Output is correct
5 Correct 9 ms 15956 KB Output is correct
6 Correct 9 ms 15900 KB Output is correct
7 Correct 10 ms 15964 KB Output is correct
8 Correct 9 ms 15896 KB Output is correct
9 Correct 9 ms 15960 KB Output is correct
10 Correct 8 ms 15900 KB Output is correct
11 Correct 9 ms 15928 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15888 KB Output is correct
2 Correct 9 ms 15832 KB Output is correct
3 Correct 9 ms 15828 KB Output is correct
4 Correct 10 ms 15848 KB Output is correct
5 Correct 9 ms 15884 KB Output is correct
6 Correct 8 ms 15808 KB Output is correct
7 Correct 636 ms 184188 KB Output is correct
8 Correct 1441 ms 377044 KB Output is correct
9 Correct 1483 ms 378996 KB Output is correct
10 Correct 1476 ms 378908 KB Output is correct
11 Correct 507 ms 202292 KB Output is correct
12 Correct 1162 ms 364736 KB Output is correct
13 Correct 1305 ms 384172 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15956 KB Output is correct
2 Correct 9 ms 16400 KB Output is correct
3 Correct 10 ms 16336 KB Output is correct
4 Correct 9 ms 16340 KB Output is correct
5 Correct 9 ms 16340 KB Output is correct
6 Correct 9 ms 16340 KB Output is correct
7 Correct 11 ms 16268 KB Output is correct
8 Correct 9 ms 16076 KB Output is correct
9 Correct 9 ms 16340 KB Output is correct
10 Correct 9 ms 16400 KB Output is correct
11 Correct 9 ms 16320 KB Output is correct
12 Correct 9 ms 16340 KB Output is correct
13 Correct 10 ms 15888 KB Output is correct
14 Correct 9 ms 15888 KB Output is correct
15 Correct 8 ms 15956 KB Output is correct
16 Correct 8 ms 15872 KB Output is correct
17 Correct 18 ms 17944 KB Output is correct
18 Correct 15 ms 17948 KB Output is correct
19 Correct 15 ms 17948 KB Output is correct
20 Correct 14 ms 17744 KB Output is correct
21 Correct 15 ms 17876 KB Output is correct
22 Correct 14 ms 17848 KB Output is correct
23 Correct 15 ms 17832 KB Output is correct
24 Correct 12 ms 17228 KB Output is correct
25 Correct 79 ms 25240 KB Output is correct
26 Correct 76 ms 25288 KB Output is correct
27 Correct 78 ms 25300 KB Output is correct
28 Correct 60 ms 24068 KB Output is correct
29 Correct 71 ms 24940 KB Output is correct
30 Correct 71 ms 25080 KB Output is correct
31 Correct 69 ms 24736 KB Output is correct
32 Correct 71 ms 24732 KB Output is correct
33 Correct 2434 ms 77252 KB Output is correct
34 Correct 2529 ms 77364 KB Output is correct
35 Correct 2527 ms 77248 KB Output is correct
36 Correct 2474 ms 77244 KB Output is correct
37 Correct 3092 ms 107712 KB Output is correct
38 Correct 3120 ms 107628 KB Output is correct
39 Correct 3201 ms 107636 KB Output is correct
40 Correct 2847 ms 102164 KB Output is correct
41 Correct 109 ms 44476 KB Output is correct
42 Correct 2622 ms 94780 KB Output is correct
43 Correct 3076 ms 106280 KB Output is correct
44 Correct 3146 ms 106752 KB Output is correct
45 Correct 1168 ms 70492 KB Output is correct
46 Correct 1090 ms 68448 KB Output is correct
47 Correct 2853 ms 101520 KB Output is correct
48 Correct 3084 ms 101896 KB Output is correct
49 Correct 23 ms 15868 KB Output is correct
50 Correct 19 ms 15976 KB Output is correct
51 Correct 8 ms 15828 KB Output is correct
52 Correct 9 ms 15880 KB Output is correct
53 Correct 9 ms 15956 KB Output is correct
54 Correct 9 ms 15900 KB Output is correct
55 Correct 10 ms 15964 KB Output is correct
56 Correct 9 ms 15896 KB Output is correct
57 Correct 9 ms 15960 KB Output is correct
58 Correct 8 ms 15900 KB Output is correct
59 Correct 9 ms 15928 KB Output is correct
60 Correct 8 ms 15808 KB Output is correct
61 Correct 636 ms 184188 KB Output is correct
62 Correct 1441 ms 377044 KB Output is correct
63 Correct 1483 ms 378996 KB Output is correct
64 Correct 1476 ms 378908 KB Output is correct
65 Correct 507 ms 202292 KB Output is correct
66 Correct 1162 ms 364736 KB Output is correct
67 Correct 1305 ms 384172 KB Output is correct
68 Correct 10 ms 15888 KB Output is correct
69 Correct 9 ms 15832 KB Output is correct
70 Correct 9 ms 15828 KB Output is correct
71 Correct 10 ms 15848 KB Output is correct
72 Correct 9 ms 15884 KB Output is correct
73 Incorrect 211 ms 65100 KB Unexpected end of file - token expected
74 Halted 0 ms 0 KB -