oj.uz

Submission #596310

# Submission time Handle Problem Language Result Execution time Memory
596310 2022-07-14T15:07:05 Z Koosha_mv Rectangles (IOI19_rect) C++14
100 / 100
 3901 ms 796384 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=2555,inf=1e8;

int n,m,a[N][N],L[N][N],D[N][N],U[N][N],R[N][N],fen[N][N],dp[N],mark[N],lupd[N][N],pd[N][N];
vector<int> lv[N][N];
vector<pair<int,int>> uv[N][N];
ll ans;

void ad(int x,int y,int val){
	for(y+=2;y>0;y-=(y&-y)){
		fen[x][y]+=val;
	}
}
int gt(int x,int y){
	int res=0;
	for(y+=2;y<N;y+=(y&-y)){
		res+=fen[x][y];
	}
	return res;
}
void add(int x,int y,int val){
	for(x+=2;x<N;x+=(x&-x)){
		ad(x,y,val);
	}
}
int get(int x,int y){
	int res=0;
	for(x+=2;x>0;x-=(x&-x)){
		res+=gt(x,y);
	}
	return res;
}
void do_it(){
	f(i,1,n+1){
		f(j,1,m+1){
			U[i][j]=i-1;
			while(a[U[i][j]][j]<a[i][j]){
				U[i][j]=U[U[i][j]][j];
			}
			L[i][j]=j-1;
			while(a[i][L[i][j]]<a[i][j]){
				L[i][j]=L[i][L[i][j]];
			}
			if(U[i][j] && a[U[i][j]][j]!=a[i][j] && U[i][j]!=i-1){
				uv[i][j].pb({U[i][j],0});
			}			
			if(L[i][j] && a[i][L[i][j]]!=a[i][j] && L[i][j]!=j-1){
				lv[i][j].pb(L[i][j]);
			}
		}
	}
	f_(i,n,1){
		f_(j,m,1){
			D[i][j]=i+1;
			while(a[D[i][j]][j]<a[i][j]){
				D[i][j]=D[D[i][j]][j];
			}
			R[i][j]=j+1;
			while(a[i][R[i][j]]<a[i][j]){
				R[i][j]=R[i][R[i][j]];
			}
			if(D[i][j]<=n && D[i][j]!=i+1){
				uv[D[i][j]][j].pb({i,0});
			}
			if(R[i][j]<=m && R[i][j]!=j+1){
				lv[i][R[i][j]].pb(j);
			}
		}
	}
}
void edame(){
	f(i,1,n+1){
		f(j,1,m+1){
			f(k,0,int(uv[i][j].size())){
				int x=uv[i][j][k].F;
				lupd[x][j]=i;
				pd[x][j]=j;
				if(lupd[x][j-1]==i){
					pd[x][j]=pd[x][j-1];
				}
				uv[i][j][k].S=pd[x][j];
			}
		}
	}
}
void solve(int y){
	fill(dp,dp+N,N);
	fill(mark,mark+N,0);
	f(x,2,n){
		for(auto u : lv[x][y]){
			mark[u]=x;
			if(dp[u]==N){
				dp[u]=x;
			}
			add(dp[u],u,1);
		}
		for(auto u : lv[x-1][y]){
			if(mark[u]==x-1){
				dp[u]=N;
			}
		}
		for(auto p : uv[x+1][y-1]){
			ans+=get(p.F+1,p.S-1);
		}
		for(auto u : lv[x][y]){
			add(dp[u],u,-1);
		}
	}
}
ll count_rectangles(vector<vector<int>> T) {
	n=T.size(),m=T[0].size();
	f(i,0,n){
		f(j,0,m){
			a[i+1][j+1]=T[i][j]+1;
		}
	}
	f(i,0,n+2){
		f(j,0,m+2){
			if(a[i][j]) continue ;
			a[i][j]=inf;
		}
	}
	do_it();
	edame();
	f(i,3,m+1){
		solve(i);
	}
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 307076 KB Output is correct
2 Correct 145 ms 307860 KB Output is correct
3 Correct 139 ms 307812 KB Output is correct
4 Correct 152 ms 307852 KB Output is correct
5 Correct 143 ms 307536 KB Output is correct
6 Correct 139 ms 307920 KB Output is correct
7 Correct 152 ms 307904 KB Output is correct
8 Correct 143 ms 307260 KB Output is correct
9 Correct 141 ms 307868 KB Output is correct
10 Correct 140 ms 307916 KB Output is correct
11 Correct 146 ms 307848 KB Output is correct
12 Correct 155 ms 307816 KB Output is correct
13 Correct 145 ms 306860 KB Output is correct
14 Correct 139 ms 307140 KB Output is correct
15 Correct 147 ms 307092 KB Output is correct
16 Correct 145 ms 306988 KB Output is correct
17 Correct 139 ms 306872 KB Output is correct
18 Correct 146 ms 306880 KB Output is correct
19 Correct 142 ms 307912 KB Output is correct
20 Correct 146 ms 307492 KB Output is correct
21 Correct 140 ms 307100 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 307076 KB Output is correct
2 Correct 145 ms 307860 KB Output is correct
3 Correct 139 ms 307812 KB Output is correct
4 Correct 152 ms 307852 KB Output is correct
5 Correct 143 ms 307536 KB Output is correct
6 Correct 139 ms 307920 KB Output is correct
7 Correct 152 ms 307904 KB Output is correct
8 Correct 143 ms 307260 KB Output is correct
9 Correct 141 ms 307868 KB Output is correct
10 Correct 140 ms 307916 KB Output is correct
11 Correct 146 ms 307848 KB Output is correct
12 Correct 155 ms 307816 KB Output is correct
13 Correct 145 ms 306860 KB Output is correct
14 Correct 139 ms 307140 KB Output is correct
15 Correct 147 ms 307092 KB Output is correct
16 Correct 145 ms 306988 KB Output is correct
17 Correct 139 ms 306872 KB Output is correct
18 Correct 146 ms 306880 KB Output is correct
19 Correct 142 ms 307912 KB Output is correct
20 Correct 146 ms 307492 KB Output is correct
21 Correct 140 ms 307100 KB Output is correct
22 Correct 148 ms 309508 KB Output is correct
23 Correct 150 ms 309536 KB Output is correct
24 Correct 144 ms 309564 KB Output is correct
25 Correct 158 ms 309848 KB Output is correct
26 Correct 145 ms 309964 KB Output is correct
27 Correct 143 ms 309928 KB Output is correct
28 Correct 148 ms 309908 KB Output is correct
29 Correct 155 ms 309756 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 307076 KB Output is correct
2 Correct 145 ms 307860 KB Output is correct
3 Correct 139 ms 307812 KB Output is correct
4 Correct 152 ms 307852 KB Output is correct
5 Correct 143 ms 307536 KB Output is correct
6 Correct 139 ms 307920 KB Output is correct
7 Correct 152 ms 307904 KB Output is correct
8 Correct 143 ms 307260 KB Output is correct
9 Correct 141 ms 307868 KB Output is correct
10 Correct 140 ms 307916 KB Output is correct
11 Correct 146 ms 307848 KB Output is correct
12 Correct 155 ms 307816 KB Output is correct
13 Correct 145 ms 306860 KB Output is correct
14 Correct 139 ms 307140 KB Output is correct
15 Correct 147 ms 307092 KB Output is correct
16 Correct 145 ms 306988 KB Output is correct
17 Correct 148 ms 309508 KB Output is correct
18 Correct 150 ms 309536 KB Output is correct
19 Correct 144 ms 309564 KB Output is correct
20 Correct 158 ms 309848 KB Output is correct
21 Correct 145 ms 309964 KB Output is correct
22 Correct 143 ms 309928 KB Output is correct
23 Correct 148 ms 309908 KB Output is correct
24 Correct 155 ms 309756 KB Output is correct
25 Correct 139 ms 306872 KB Output is correct
26 Correct 146 ms 306880 KB Output is correct
27 Correct 142 ms 307912 KB Output is correct
28 Correct 146 ms 307492 KB Output is correct
29 Correct 140 ms 307100 KB Output is correct
30 Correct 152 ms 314664 KB Output is correct
31 Correct 152 ms 314660 KB Output is correct
32 Correct 163 ms 314600 KB Output is correct
33 Correct 155 ms 315784 KB Output is correct
34 Correct 162 ms 316320 KB Output is correct
35 Correct 162 ms 316408 KB Output is correct
36 Correct 173 ms 316312 KB Output is correct
37 Correct 160 ms 316116 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 307076 KB Output is correct
2 Correct 145 ms 307860 KB Output is correct
3 Correct 139 ms 307812 KB Output is correct
4 Correct 152 ms 307852 KB Output is correct
5 Correct 143 ms 307536 KB Output is correct
6 Correct 139 ms 307920 KB Output is correct
7 Correct 152 ms 307904 KB Output is correct
8 Correct 143 ms 307260 KB Output is correct
9 Correct 141 ms 307868 KB Output is correct
10 Correct 140 ms 307916 KB Output is correct
11 Correct 146 ms 307848 KB Output is correct
12 Correct 155 ms 307816 KB Output is correct
13 Correct 145 ms 306860 KB Output is correct
14 Correct 139 ms 307140 KB Output is correct
15 Correct 147 ms 307092 KB Output is correct
16 Correct 145 ms 306988 KB Output is correct
17 Correct 148 ms 309508 KB Output is correct
18 Correct 150 ms 309536 KB Output is correct
19 Correct 144 ms 309564 KB Output is correct
20 Correct 158 ms 309848 KB Output is correct
21 Correct 145 ms 309964 KB Output is correct
22 Correct 143 ms 309928 KB Output is correct
23 Correct 148 ms 309908 KB Output is correct
24 Correct 155 ms 309756 KB Output is correct
25 Correct 152 ms 314664 KB Output is correct
26 Correct 152 ms 314660 KB Output is correct
27 Correct 163 ms 314600 KB Output is correct
28 Correct 155 ms 315784 KB Output is correct
29 Correct 162 ms 316320 KB Output is correct
30 Correct 162 ms 316408 KB Output is correct
31 Correct 173 ms 316312 KB Output is correct
32 Correct 160 ms 316116 KB Output is correct
33 Correct 139 ms 306872 KB Output is correct
34 Correct 146 ms 306880 KB Output is correct
35 Correct 142 ms 307912 KB Output is correct
36 Correct 146 ms 307492 KB Output is correct
37 Correct 140 ms 307100 KB Output is correct
38 Correct 227 ms 350024 KB Output is correct
39 Correct 272 ms 355404 KB Output is correct
40 Correct 258 ms 352888 KB Output is correct
41 Correct 299 ms 358240 KB Output is correct
42 Correct 296 ms 352404 KB Output is correct
43 Correct 297 ms 352380 KB Output is correct
44 Correct 331 ms 352444 KB Output is correct
45 Correct 289 ms 349696 KB Output is correct
46 Correct 254 ms 356156 KB Output is correct
47 Correct 286 ms 358708 KB Output is correct
48 Correct 406 ms 366724 KB Output is correct
49 Correct 422 ms 367244 KB Output is correct
50 Correct 278 ms 348112 KB Output is correct
51 Correct 298 ms 336732 KB Output is correct
52 Correct 373 ms 365640 KB Output is correct
53 Correct 376 ms 365416 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 307448 KB Output is correct
2 Correct 147 ms 307376 KB Output is correct
3 Correct 152 ms 307184 KB Output is correct
4 Correct 148 ms 306880 KB Output is correct
5 Correct 154 ms 307616 KB Output is correct
6 Correct 157 ms 307396 KB Output is correct
7 Correct 164 ms 307488 KB Output is correct
8 Correct 148 ms 307388 KB Output is correct
9 Correct 155 ms 307432 KB Output is correct
10 Correct 153 ms 306980 KB Output is correct
11 Correct 168 ms 307096 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 306872 KB Output is correct
2 Correct 146 ms 306880 KB Output is correct
3 Correct 142 ms 307912 KB Output is correct
4 Correct 146 ms 307492 KB Output is correct
5 Correct 140 ms 307100 KB Output is correct
6 Correct 145 ms 307220 KB Output is correct
7 Correct 754 ms 472908 KB Output is correct
8 Correct 1502 ms 651968 KB Output is correct
9 Correct 1994 ms 653796 KB Output is correct
10 Correct 1514 ms 653744 KB Output is correct
11 Correct 356 ms 393088 KB Output is correct
12 Correct 611 ms 478060 KB Output is correct
13 Correct 661 ms 481076 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 307076 KB Output is correct
2 Correct 145 ms 307860 KB Output is correct
3 Correct 139 ms 307812 KB Output is correct
4 Correct 152 ms 307852 KB Output is correct
5 Correct 143 ms 307536 KB Output is correct
6 Correct 139 ms 307920 KB Output is correct
7 Correct 152 ms 307904 KB Output is correct
8 Correct 143 ms 307260 KB Output is correct
9 Correct 141 ms 307868 KB Output is correct
10 Correct 140 ms 307916 KB Output is correct
11 Correct 146 ms 307848 KB Output is correct
12 Correct 155 ms 307816 KB Output is correct
13 Correct 145 ms 306860 KB Output is correct
14 Correct 139 ms 307140 KB Output is correct
15 Correct 147 ms 307092 KB Output is correct
16 Correct 145 ms 306988 KB Output is correct
17 Correct 148 ms 309508 KB Output is correct
18 Correct 150 ms 309536 KB Output is correct
19 Correct 144 ms 309564 KB Output is correct
20 Correct 158 ms 309848 KB Output is correct
21 Correct 145 ms 309964 KB Output is correct
22 Correct 143 ms 309928 KB Output is correct
23 Correct 148 ms 309908 KB Output is correct
24 Correct 155 ms 309756 KB Output is correct
25 Correct 152 ms 314664 KB Output is correct
26 Correct 152 ms 314660 KB Output is correct
27 Correct 163 ms 314600 KB Output is correct
28 Correct 155 ms 315784 KB Output is correct
29 Correct 162 ms 316320 KB Output is correct
30 Correct 162 ms 316408 KB Output is correct
31 Correct 173 ms 316312 KB Output is correct
32 Correct 160 ms 316116 KB Output is correct
33 Correct 227 ms 350024 KB Output is correct
34 Correct 272 ms 355404 KB Output is correct
35 Correct 258 ms 352888 KB Output is correct
36 Correct 299 ms 358240 KB Output is correct
37 Correct 296 ms 352404 KB Output is correct
38 Correct 297 ms 352380 KB Output is correct
39 Correct 331 ms 352444 KB Output is correct
40 Correct 289 ms 349696 KB Output is correct
41 Correct 254 ms 356156 KB Output is correct
42 Correct 286 ms 358708 KB Output is correct
43 Correct 406 ms 366724 KB Output is correct
44 Correct 422 ms 367244 KB Output is correct
45 Correct 278 ms 348112 KB Output is correct
46 Correct 298 ms 336732 KB Output is correct
47 Correct 373 ms 365640 KB Output is correct
48 Correct 376 ms 365416 KB Output is correct
49 Correct 152 ms 307448 KB Output is correct
50 Correct 147 ms 307376 KB Output is correct
51 Correct 152 ms 307184 KB Output is correct
52 Correct 148 ms 306880 KB Output is correct
53 Correct 154 ms 307616 KB Output is correct
54 Correct 157 ms 307396 KB Output is correct
55 Correct 164 ms 307488 KB Output is correct
56 Correct 148 ms 307388 KB Output is correct
57 Correct 155 ms 307432 KB Output is correct
58 Correct 153 ms 306980 KB Output is correct
59 Correct 168 ms 307096 KB Output is correct
60 Correct 145 ms 307220 KB Output is correct
61 Correct 754 ms 472908 KB Output is correct
62 Correct 1502 ms 651968 KB Output is correct
63 Correct 1994 ms 653796 KB Output is correct
64 Correct 1514 ms 653744 KB Output is correct
65 Correct 356 ms 393088 KB Output is correct
66 Correct 611 ms 478060 KB Output is correct
67 Correct 661 ms 481076 KB Output is correct
68 Correct 139 ms 306872 KB Output is correct
69 Correct 146 ms 306880 KB Output is correct
70 Correct 142 ms 307912 KB Output is correct
71 Correct 146 ms 307492 KB Output is correct
72 Correct 140 ms 307100 KB Output is correct
73 Correct 1355 ms 591112 KB Output is correct
74 Correct 1720 ms 664668 KB Output is correct
75 Correct 1590 ms 636140 KB Output is correct
76 Correct 1897 ms 709736 KB Output is correct
77 Correct 2461 ms 635492 KB Output is correct
78 Correct 2184 ms 597240 KB Output is correct
79 Correct 2414 ms 689536 KB Output is correct
80 Correct 3823 ms 791232 KB Output is correct
81 Correct 2199 ms 600340 KB Output is correct
82 Correct 3099 ms 738284 KB Output is correct
83 Correct 3901 ms 796384 KB Output is correct
84 Correct 2303 ms 588512 KB Output is correct
85 Correct 3474 ms 778340 KB Output is correct
86 Correct 3279 ms 764620 KB Output is correct
87 Correct 1513 ms 571332 KB Output is correct
88 Correct 2361 ms 635776 KB Output is correct
89 Correct 2390 ms 635544 KB Output is correct
90 Correct 2383 ms 635436 KB Output is correct