oj.uz

Submission #348125

# Submission time Handle Problem Language Result Execution time Memory
348125 2021-01-14T09:46:54 Z Kerim Rectangles (IOI19_rect) C++17
100 / 100
 4513 ms 650252 KB 
#include "rect.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x,y,z)  cerr<< #x <<" = "<< x<<" "<< #y <<" = "<< y<<" "<< #z <<" = "<< z<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N=2505;
int ata[N],mn[N],mx[N],arr[N],c[N],sz,sub[N],vis[N],rc,pos;
vector<int>row[N][N],col[N][N];
vector<pair<PII,int> >addc[N];
vector<PII>remc[N];
int F[N][N];
bool cmp(int x,int y){
	return (arr[x]<arr[y]);	
}
int tap(int x){
	if(ata[x]==x)return x;
	return ata[x]=tap(ata[x]);	
}
void merge(int x,int y){
	if((x=tap(x))==(y=tap(y)))return;
	if(sub[x]<sub[y])swap(x,y);
	ata[y]=x;sub[x]+=sub[y];
	umin(mn[x],mn[y]);
	umax(mx[x],mx[y]);	
}
//The key idea is there are at most 2*n^2 such pairs
void add(int x,int y){
	assert(x+1<y);
	//if rc=0, then rectangle on row (pos) in range (arr[pos][x],arr[pos][y]) is good
	//if rc=1, then rectangle on column (pos) in range (arr[x][pos],arr[y][pos]) is good
	if(!rc)row[x][y].pb(pos);
	else col[x][y].pb(pos);
}
void solve(int x){
	if(x>1 and vis[x-1]){
		int a=mn[tap(x-1)]-1;
		if(a>=1)add(a,x);
	}	
	if(x<sz and vis[x+1]){
		int b=mx[tap(x+1)]+1;
		if(b<=sz)add(x,b);
	}
}
void upd(int x){
	vis[x]=1;
	if(x>1 and vis[x-1])merge(x-1,x);
	if(x<sz and vis[x+1])merge(x,x+1);	
}
void f(){
	for(int i=1;i<=sz;i++)
    	ata[i]=mn[i]=mx[i]=i,sub[i]=1,c[i]=i,vis[i]=0;
    sort(c+1,c+sz+1,cmp);
    for(int i=1;i<=sz;i++){
    	int j=i;
		while(j<=sz and arr[c[j]]==arr[c[i]])solve(c[j++]);
		for(int k=i;k<j;k++)upd(c[k]);
		i=j-1;
    }
}
void upd(int y,int x,int val){
	for(;x<N;x+=x&(-x))F[y][x]+=val;	
}
int get(int y,int x){
	int res=0;
	for(;x;x-=x&(-x))res+=F[y][x];
	return res;
}	
void relax(int tt,int x,int y){
	if(!tt)
		row[x][y].erase(unique(all(row[x][y])),row[x][y].end());
	else
		col[x][y].erase(unique(all(col[x][y])),col[x][y].end());
		
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	int n=int(a.size()),m=int(a[0].size());
	if(n<3 or m<3)
		return 0;
	{
		sz=m;
		for(int j=1;j<=n;j++){
			for(int i=1;i<=m;i++)
				arr[i]=a[j-1][i-1];
			rc=0;pos=j;f();
		}sz=n;
		for(int j=1;j<=m;j++){
			for(int i=1;i<=n;i++)
				arr[i]=a[i-1][j-1];
			rc=1;pos=j;f();
		}
	}
	int tmp,st=-1,en,cnt,who;
	for(int i=1;i<=n;i++)	
		for(int j=i+2;j<=n;j++){
			relax(1,i,j);
			tmp=int(col[i][j].size());
			for(int k=0;k<tmp;k++){
				if(st==-1)st=col[i][j][k];
				en=col[i][j][k];
				if(k+1==tmp or col[i][j][k]+1!=col[i][j][k+1]){
					for(int h=st;h<=en;h++)
						addc[h].pb(mp(mp(i+1,j-1),en));
					st=-1;
				}
			}
		}
	ll ans=0;
	for(int i=2;i<m;i++){
		tr(it,addc[i])upd(it->ff.ss,it->ff.ff,+1),remc[it->ss].pb(it->ff);
		addc[i].clear();
		for(int j=i;j<=m;j++){
			if(j<m){
				relax(0,i-1,j+1);
				tmp=int(row[i-1][j+1].size());cnt=0;
				for(int k=0;k<tmp;k++){who=row[i-1][j+1][k];
					cnt++;ans+=get(who,who)-get(who,who-cnt);
					if(k+1==tmp or who+1!=row[i-1][j+1][k+1])cnt=0;
				}
			}
			tr(it,remc[j])upd(it->ss,it->ff,-1);
			remc[j].clear();
		}
	}
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 295148 KB Output is correct
2 Correct 218 ms 295276 KB Output is correct
3 Correct 205 ms 295276 KB Output is correct
4 Correct 198 ms 295188 KB Output is correct
5 Correct 196 ms 295224 KB Output is correct
6 Correct 191 ms 295532 KB Output is correct
7 Correct 190 ms 295532 KB Output is correct
8 Correct 200 ms 295276 KB Output is correct
9 Correct 190 ms 295532 KB Output is correct
10 Correct 198 ms 295680 KB Output is correct
11 Correct 219 ms 295692 KB Output is correct
12 Correct 198 ms 295604 KB Output is correct
13 Correct 190 ms 295148 KB Output is correct
14 Correct 194 ms 295108 KB Output is correct
15 Correct 198 ms 295148 KB Output is correct
16 Correct 191 ms 295148 KB Output is correct
17 Correct 193 ms 295148 KB Output is correct
18 Correct 199 ms 295128 KB Output is correct
19 Correct 205 ms 295532 KB Output is correct
20 Correct 205 ms 295148 KB Output is correct
21 Correct 201 ms 295148 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 295148 KB Output is correct
2 Correct 218 ms 295276 KB Output is correct
3 Correct 205 ms 295276 KB Output is correct
4 Correct 198 ms 295188 KB Output is correct
5 Correct 196 ms 295224 KB Output is correct
6 Correct 191 ms 295532 KB Output is correct
7 Correct 190 ms 295532 KB Output is correct
8 Correct 200 ms 295276 KB Output is correct
9 Correct 190 ms 295532 KB Output is correct
10 Correct 198 ms 295680 KB Output is correct
11 Correct 219 ms 295692 KB Output is correct
12 Correct 198 ms 295604 KB Output is correct
13 Correct 190 ms 295148 KB Output is correct
14 Correct 194 ms 295108 KB Output is correct
15 Correct 198 ms 295148 KB Output is correct
16 Correct 191 ms 295148 KB Output is correct
17 Correct 203 ms 295532 KB Output is correct
18 Correct 199 ms 295516 KB Output is correct
19 Correct 195 ms 295532 KB Output is correct
20 Correct 201 ms 296172 KB Output is correct
21 Correct 192 ms 296300 KB Output is correct
22 Correct 195 ms 296300 KB Output is correct
23 Correct 194 ms 296300 KB Output is correct
24 Correct 194 ms 296044 KB Output is correct
25 Correct 193 ms 295148 KB Output is correct
26 Correct 199 ms 295128 KB Output is correct
27 Correct 205 ms 295532 KB Output is correct
28 Correct 205 ms 295148 KB Output is correct
29 Correct 201 ms 295148 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 295148 KB Output is correct
2 Correct 218 ms 295276 KB Output is correct
3 Correct 205 ms 295276 KB Output is correct
4 Correct 198 ms 295188 KB Output is correct
5 Correct 196 ms 295224 KB Output is correct
6 Correct 191 ms 295532 KB Output is correct
7 Correct 190 ms 295532 KB Output is correct
8 Correct 200 ms 295276 KB Output is correct
9 Correct 190 ms 295532 KB Output is correct
10 Correct 198 ms 295680 KB Output is correct
11 Correct 219 ms 295692 KB Output is correct
12 Correct 198 ms 295604 KB Output is correct
13 Correct 190 ms 295148 KB Output is correct
14 Correct 194 ms 295108 KB Output is correct
15 Correct 198 ms 295148 KB Output is correct
16 Correct 191 ms 295148 KB Output is correct
17 Correct 203 ms 295532 KB Output is correct
18 Correct 199 ms 295516 KB Output is correct
19 Correct 195 ms 295532 KB Output is correct
20 Correct 201 ms 296172 KB Output is correct
21 Correct 192 ms 296300 KB Output is correct
22 Correct 195 ms 296300 KB Output is correct
23 Correct 194 ms 296300 KB Output is correct
24 Correct 194 ms 296044 KB Output is correct
25 Correct 202 ms 296556 KB Output is correct
26 Correct 204 ms 296556 KB Output is correct
27 Correct 206 ms 296600 KB Output is correct
28 Correct 206 ms 298348 KB Output is correct
29 Correct 217 ms 299244 KB Output is correct
30 Correct 212 ms 299244 KB Output is correct
31 Correct 209 ms 298988 KB Output is correct
32 Correct 209 ms 298860 KB Output is correct
33 Correct 193 ms 295148 KB Output is correct
34 Correct 199 ms 295128 KB Output is correct
35 Correct 205 ms 295532 KB Output is correct
36 Correct 205 ms 295148 KB Output is correct
37 Correct 201 ms 295148 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 295148 KB Output is correct
2 Correct 218 ms 295276 KB Output is correct
3 Correct 205 ms 295276 KB Output is correct
4 Correct 198 ms 295188 KB Output is correct
5 Correct 196 ms 295224 KB Output is correct
6 Correct 191 ms 295532 KB Output is correct
7 Correct 190 ms 295532 KB Output is correct
8 Correct 200 ms 295276 KB Output is correct
9 Correct 190 ms 295532 KB Output is correct
10 Correct 198 ms 295680 KB Output is correct
11 Correct 219 ms 295692 KB Output is correct
12 Correct 198 ms 295604 KB Output is correct
13 Correct 190 ms 295148 KB Output is correct
14 Correct 194 ms 295108 KB Output is correct
15 Correct 198 ms 295148 KB Output is correct
16 Correct 191 ms 295148 KB Output is correct
17 Correct 203 ms 295532 KB Output is correct
18 Correct 199 ms 295516 KB Output is correct
19 Correct 195 ms 295532 KB Output is correct
20 Correct 201 ms 296172 KB Output is correct
21 Correct 192 ms 296300 KB Output is correct
22 Correct 195 ms 296300 KB Output is correct
23 Correct 194 ms 296300 KB Output is correct
24 Correct 194 ms 296044 KB Output is correct
25 Correct 202 ms 296556 KB Output is correct
26 Correct 204 ms 296556 KB Output is correct
27 Correct 206 ms 296600 KB Output is correct
28 Correct 206 ms 298348 KB Output is correct
29 Correct 217 ms 299244 KB Output is correct
30 Correct 212 ms 299244 KB Output is correct
31 Correct 209 ms 298988 KB Output is correct
32 Correct 209 ms 298860 KB Output is correct
33 Correct 401 ms 328556 KB Output is correct
34 Correct 363 ms 328556 KB Output is correct
35 Correct 387 ms 328332 KB Output is correct
36 Correct 329 ms 328428 KB Output is correct
37 Correct 415 ms 313324 KB Output is correct
38 Correct 406 ms 313316 KB Output is correct
39 Correct 409 ms 313328 KB Output is correct
40 Correct 396 ms 312684 KB Output is correct
41 Correct 316 ms 312580 KB Output is correct
42 Correct 332 ms 316268 KB Output is correct
43 Correct 473 ms 328260 KB Output is correct
44 Correct 474 ms 328456 KB Output is correct
45 Correct 324 ms 316140 KB Output is correct
46 Correct 315 ms 312684 KB Output is correct
47 Correct 418 ms 323948 KB Output is correct
48 Correct 433 ms 324076 KB Output is correct
49 Correct 193 ms 295148 KB Output is correct
50 Correct 199 ms 295128 KB Output is correct
51 Correct 205 ms 295532 KB Output is correct
52 Correct 205 ms 295148 KB Output is correct
53 Correct 201 ms 295148 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 295532 KB Output is correct
2 Correct 214 ms 295404 KB Output is correct
3 Correct 224 ms 295532 KB Output is correct
4 Correct 192 ms 295148 KB Output is correct
5 Correct 222 ms 295520 KB Output is correct
6 Correct 224 ms 295556 KB Output is correct
7 Correct 223 ms 295532 KB Output is correct
8 Correct 226 ms 295532 KB Output is correct
9 Correct 222 ms 295532 KB Output is correct
10 Correct 193 ms 295148 KB Output is correct
11 Correct 194 ms 295148 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 295276 KB Output is correct
2 Correct 949 ms 373116 KB Output is correct
3 Correct 1814 ms 455020 KB Output is correct
4 Correct 1842 ms 455404 KB Output is correct
5 Correct 1843 ms 455532 KB Output is correct
6 Correct 536 ms 320876 KB Output is correct
7 Correct 888 ms 342636 KB Output is correct
8 Correct 936 ms 345708 KB Output is correct
9 Correct 193 ms 295148 KB Output is correct
10 Correct 199 ms 295128 KB Output is correct
11 Correct 205 ms 295532 KB Output is correct
12 Correct 205 ms 295148 KB Output is correct
13 Correct 201 ms 295148 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 295148 KB Output is correct
2 Correct 218 ms 295276 KB Output is correct
3 Correct 205 ms 295276 KB Output is correct
4 Correct 198 ms 295188 KB Output is correct
5 Correct 196 ms 295224 KB Output is correct
6 Correct 191 ms 295532 KB Output is correct
7 Correct 190 ms 295532 KB Output is correct
8 Correct 200 ms 295276 KB Output is correct
9 Correct 190 ms 295532 KB Output is correct
10 Correct 198 ms 295680 KB Output is correct
11 Correct 219 ms 295692 KB Output is correct
12 Correct 198 ms 295604 KB Output is correct
13 Correct 190 ms 295148 KB Output is correct
14 Correct 194 ms 295108 KB Output is correct
15 Correct 198 ms 295148 KB Output is correct
16 Correct 191 ms 295148 KB Output is correct
17 Correct 203 ms 295532 KB Output is correct
18 Correct 199 ms 295516 KB Output is correct
19 Correct 195 ms 295532 KB Output is correct
20 Correct 201 ms 296172 KB Output is correct
21 Correct 192 ms 296300 KB Output is correct
22 Correct 195 ms 296300 KB Output is correct
23 Correct 194 ms 296300 KB Output is correct
24 Correct 194 ms 296044 KB Output is correct
25 Correct 202 ms 296556 KB Output is correct
26 Correct 204 ms 296556 KB Output is correct
27 Correct 206 ms 296600 KB Output is correct
28 Correct 206 ms 298348 KB Output is correct
29 Correct 217 ms 299244 KB Output is correct
30 Correct 212 ms 299244 KB Output is correct
31 Correct 209 ms 298988 KB Output is correct
32 Correct 209 ms 298860 KB Output is correct
33 Correct 401 ms 328556 KB Output is correct
34 Correct 363 ms 328556 KB Output is correct
35 Correct 387 ms 328332 KB Output is correct
36 Correct 329 ms 328428 KB Output is correct
37 Correct 415 ms 313324 KB Output is correct
38 Correct 406 ms 313316 KB Output is correct
39 Correct 409 ms 313328 KB Output is correct
40 Correct 396 ms 312684 KB Output is correct
41 Correct 316 ms 312580 KB Output is correct
42 Correct 332 ms 316268 KB Output is correct
43 Correct 473 ms 328260 KB Output is correct
44 Correct 474 ms 328456 KB Output is correct
45 Correct 324 ms 316140 KB Output is correct
46 Correct 315 ms 312684 KB Output is correct
47 Correct 418 ms 323948 KB Output is correct
48 Correct 433 ms 324076 KB Output is correct
49 Correct 221 ms 295532 KB Output is correct
50 Correct 214 ms 295404 KB Output is correct
51 Correct 224 ms 295532 KB Output is correct
52 Correct 192 ms 295148 KB Output is correct
53 Correct 222 ms 295520 KB Output is correct
54 Correct 224 ms 295556 KB Output is correct
55 Correct 223 ms 295532 KB Output is correct
56 Correct 226 ms 295532 KB Output is correct
57 Correct 222 ms 295532 KB Output is correct
58 Correct 193 ms 295148 KB Output is correct
59 Correct 194 ms 295148 KB Output is correct
60 Correct 194 ms 295276 KB Output is correct
61 Correct 949 ms 373116 KB Output is correct
62 Correct 1814 ms 455020 KB Output is correct
63 Correct 1842 ms 455404 KB Output is correct
64 Correct 1843 ms 455532 KB Output is correct
65 Correct 536 ms 320876 KB Output is correct
66 Correct 888 ms 342636 KB Output is correct
67 Correct 936 ms 345708 KB Output is correct
68 Correct 3500 ms 644216 KB Output is correct
69 Correct 2760 ms 648812 KB Output is correct
70 Correct 3012 ms 643996 KB Output is correct
71 Correct 2144 ms 644036 KB Output is correct
72 Correct 3961 ms 526240 KB Output is correct
73 Correct 2566 ms 494296 KB Output is correct
74 Correct 2849 ms 524516 KB Output is correct
75 Correct 4200 ms 615252 KB Output is correct
76 Correct 2702 ms 511596 KB Output is correct
77 Correct 3709 ms 587756 KB Output is correct
78 Correct 4513 ms 650252 KB Output is correct
79 Correct 2351 ms 477292 KB Output is correct
80 Correct 4011 ms 618644 KB Output is correct
81 Correct 3869 ms 611560 KB Output is correct
82 Correct 2335 ms 457708 KB Output is correct
83 Correct 3893 ms 569048 KB Output is correct
84 Correct 3865 ms 569196 KB Output is correct
85 Correct 3904 ms 569188 KB Output is correct
86 Correct 193 ms 295148 KB Output is correct
87 Correct 199 ms 295128 KB Output is correct
88 Correct 205 ms 295532 KB Output is correct
89 Correct 205 ms 295148 KB Output is correct
90 Correct 201 ms 295148 KB Output is correct