oj.uz

답안 #443546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443546 2021-07-10T17:54:11 Z vanic Rectangles (IOI19_rect) C++14
100 / 100
 3462 ms 574944 KB 
#include "rect.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
 
typedef long long ll;
 
const int maxn=2503, Log=12, pot=(1<<Log);
const int inf=1e9;
ll sol;
int svi[maxn][maxn][4];
int n, m;
ll bio[maxn*maxn];
int svi1[maxn][maxn][4];


struct tmin{
	int t[pot*2];
	void update(int x, int val){
		t[x]=val;
	}
	void gradi(){
		for(int x=pot-1; x>0; x--){
			t[x]=min(t[x*2], t[x*2+1]);
		}
	}
	int query(int l, int r){
		int sol=inf;
		for(l+=pot, r+=pot; l<r; l>>=1, r>>=1){
			if(l&1){
				sol=min(sol, t[l++]);
			}
			if(r&1){
				sol=min(sol, t[--r]);
			}
		}
		return sol;
	}
};
 
struct tmax{
	int t[pot*2];
	void update(int x, int val){
		t[x]=val;
	}
	void gradi(){
		for(int x=pot-1; x>0; x--){
			t[x]=max(t[x*2], t[x*2+1]);
		}
	}
	int query(int l, int r){
		int sol=0;
		for(l+=pot, r+=pot; l<r; l>>=1, r>>=1){
			if(l&1){
				sol=max(sol, t[l++]);
			}
			if(r&1){
				sol=max(sol, t[--r]);
			}
		}
		return sol;
	}
};
 
tmin R1[maxn], C1[maxn];
tmax R2[maxn], C2[maxn];
pair < int, int > v[maxn];

 
ll count_rectangles(vector < vector < int > > a){
	n=a.size();
	m=a[0].size();
	int indeks=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			while(indeks && v[indeks-1].first<a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi1[i][j][2]=0;
			}
			else{
				svi1[i][j][2]=v[indeks-1].second+1;
			}
 
 
			while(indeks && v[indeks-1].first<=a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi[i][j][2]=0;
			}
			else{
				svi[i][j][2]=v[indeks-1].second+1;
			}
			v[indeks]={a[i][j], j};
			indeks++;
		}
		indeks=0;
		for(int j=m-1; j>-1; j--){
			while(indeks && v[indeks-1].first<a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi1[i][j][3]=m-1;
			}
			else{
				svi1[i][j][3]=v[indeks-1].second-1;
			}
			
			
			while(indeks && v[indeks-1].first<=a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi[i][j][3]=m-1;
			}
			else{
				svi[i][j][3]=v[indeks-1].second-1;
			}
			v[indeks]={a[i][j], j};
			indeks++;
		}
		indeks=0;
	}
	for(int j=0; j<m; j++){
		for(int i=0; i<n; i++){
			while(indeks && v[indeks-1].first<a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi1[i][j][0]=0;
			}
			else{
				svi1[i][j][0]=v[indeks-1].second+1;
			}
 
 
 
			while(indeks && v[indeks-1].first<=a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi[i][j][0]=0;
			}
			else{
				svi[i][j][0]=v[indeks-1].second+1;
			}
			v[indeks]={a[i][j], i};
			indeks++;
		}
		indeks=0;
		for(int i=n-1; i>-1; i--){
			while(indeks && v[indeks-1].first<a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi1[i][j][1]=n-1;
			}
			else{
				svi1[i][j][1]=v[indeks-1].second-1;
			}
 
 
			while(indeks && v[indeks-1].first<=a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi[i][j][1]=n-1;
			}
			else{
				svi[i][j][1]=v[indeks-1].second-1;
			}
			v[indeks]={a[i][j], i};
			indeks++;
		}
		indeks=0;
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			R1[i].update(j+pot, svi1[i][j][1]);
			R2[i].update(j+pot, svi1[i][j][0]);
			C1[j].update(i+pot, svi1[i][j][3]);
			C2[j].update(i+pot, svi1[i][j][2]);
		}
	}
	for(int i=0; i<n; i++){
		R1[i].gradi();
		R2[i].gradi();
	}
	for(int i=0; i<m; i++){
		C1[i].gradi();
		C2[i].gradi();
	}
	int c[4];
	ll br;
	indeks=0;
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			br=0;
			for(int k=0; k<4; k++){
				c[k]=svi[i][j][k];
				br*=maxn;
				br+=c[k];
			}
			if(c[0]==0 || c[2]==0 || c[1]==n-1 || c[3]==m-1){
				continue;
			}
			if(c[0]<R2[c[1]+1].query(c[2], c[3]+1)){
				continue;
			}
			if(c[1]>R1[c[0]-1].query(c[2], c[3]+1)){
				continue;
			}
			if(c[2]<C2[c[3]+1].query(c[0], c[1]+1)){
				continue;
			}
			if(c[3]>C1[c[2]-1].query(c[0], c[1]+1)){
				continue;
			}
//			cout << c[0] << ' '<< c[2] << ' ' << c[1] << ' ' << c[3] << endl;
			bio[indeks]=br;
			indeks++;
		}
	}
	sort(bio, bio+indeks);
	for(int i=0; i<indeks; i++){
		if(i==indeks-1 || bio[i]!=bio[i+1]){
			sol++;
		}
	}
	return sol;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 2892 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct
8 Correct 2 ms 2124 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 2 ms 2892 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Correct 3 ms 2892 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 2 ms 2892 KB Output is correct
20 Correct 2 ms 2380 KB Output is correct
21 Correct 1 ms 844 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 2892 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct
8 Correct 2 ms 2124 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 2 ms 2892 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Correct 3 ms 2892 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 2 ms 2892 KB Output is correct
20 Correct 2 ms 2380 KB Output is correct
21 Correct 1 ms 844 KB Output is correct
22 Correct 6 ms 7628 KB Output is correct
23 Correct 8 ms 7628 KB Output is correct
24 Correct 6 ms 7692 KB Output is correct
25 Correct 7 ms 7628 KB Output is correct
26 Correct 6 ms 7500 KB Output is correct
27 Correct 6 ms 7492 KB Output is correct
28 Correct 6 ms 7628 KB Output is correct
29 Correct 5 ms 5836 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 2892 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct
8 Correct 2 ms 2124 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 2 ms 2892 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Correct 3 ms 2892 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 6 ms 7628 KB Output is correct
18 Correct 8 ms 7628 KB Output is correct
19 Correct 6 ms 7692 KB Output is correct
20 Correct 7 ms 7628 KB Output is correct
21 Correct 6 ms 7500 KB Output is correct
22 Correct 6 ms 7492 KB Output is correct
23 Correct 6 ms 7628 KB Output is correct
24 Correct 5 ms 5836 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 2 ms 2892 KB Output is correct
28 Correct 2 ms 2380 KB Output is correct
29 Correct 1 ms 844 KB Output is correct
30 Correct 22 ms 19752 KB Output is correct
31 Correct 24 ms 19884 KB Output is correct
32 Correct 25 ms 19756 KB Output is correct
33 Correct 19 ms 19516 KB Output is correct
34 Correct 22 ms 19632 KB Output is correct
35 Correct 20 ms 19676 KB Output is correct
36 Correct 20 ms 19596 KB Output is correct
37 Correct 20 ms 19496 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 2892 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct
8 Correct 2 ms 2124 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 2 ms 2892 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Correct 3 ms 2892 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 6 ms 7628 KB Output is correct
18 Correct 8 ms 7628 KB Output is correct
19 Correct 6 ms 7692 KB Output is correct
20 Correct 7 ms 7628 KB Output is correct
21 Correct 6 ms 7500 KB Output is correct
22 Correct 6 ms 7492 KB Output is correct
23 Correct 6 ms 7628 KB Output is correct
24 Correct 5 ms 5836 KB Output is correct
25 Correct 22 ms 19752 KB Output is correct
26 Correct 24 ms 19884 KB Output is correct
27 Correct 25 ms 19756 KB Output is correct
28 Correct 19 ms 19516 KB Output is correct
29 Correct 22 ms 19632 KB Output is correct
30 Correct 20 ms 19676 KB Output is correct
31 Correct 20 ms 19596 KB Output is correct
32 Correct 20 ms 19496 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 460 KB Output is correct
35 Correct 2 ms 2892 KB Output is correct
36 Correct 2 ms 2380 KB Output is correct
37 Correct 1 ms 844 KB Output is correct
38 Correct 111 ms 81356 KB Output is correct
39 Correct 101 ms 81340 KB Output is correct
40 Correct 99 ms 81348 KB Output is correct
41 Correct 104 ms 81392 KB Output is correct
42 Correct 241 ms 85100 KB Output is correct
43 Correct 242 ms 85044 KB Output is correct
44 Correct 240 ms 85136 KB Output is correct
45 Correct 233 ms 81416 KB Output is correct
46 Correct 116 ms 81432 KB Output is correct
47 Correct 119 ms 81732 KB Output is correct
48 Correct 143 ms 82660 KB Output is correct
49 Correct 159 ms 82724 KB Output is correct
50 Correct 83 ms 58264 KB Output is correct
51 Correct 82 ms 55440 KB Output is correct
52 Correct 160 ms 83140 KB Output is correct
53 Correct 183 ms 83120 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 101060 KB Output is correct
2 Correct 62 ms 85900 KB Output is correct
3 Correct 73 ms 101072 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 73 ms 101060 KB Output is correct
6 Correct 73 ms 101096 KB Output is correct
7 Correct 76 ms 101024 KB Output is correct
8 Correct 89 ms 101060 KB Output is correct
9 Correct 78 ms 101088 KB Output is correct
10 Correct 72 ms 100684 KB Output is correct
11 Correct 76 ms 100880 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 2 ms 2380 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 694 ms 301516 KB Output is correct
8 Correct 1361 ms 526380 KB Output is correct
9 Correct 1318 ms 528308 KB Output is correct
10 Correct 1310 ms 528408 KB Output is correct
11 Correct 516 ms 310800 KB Output is correct
12 Correct 987 ms 514160 KB Output is correct
13 Correct 1052 ms 525868 KB Output is correct

Subtask #7
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 2892 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct
8 Correct 2 ms 2124 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 2 ms 2892 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Correct 3 ms 2892 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 6 ms 7628 KB Output is correct
18 Correct 8 ms 7628 KB Output is correct
19 Correct 6 ms 7692 KB Output is correct
20 Correct 7 ms 7628 KB Output is correct
21 Correct 6 ms 7500 KB Output is correct
22 Correct 6 ms 7492 KB Output is correct
23 Correct 6 ms 7628 KB Output is correct
24 Correct 5 ms 5836 KB Output is correct
25 Correct 22 ms 19752 KB Output is correct
26 Correct 24 ms 19884 KB Output is correct
27 Correct 25 ms 19756 KB Output is correct
28 Correct 19 ms 19516 KB Output is correct
29 Correct 22 ms 19632 KB Output is correct
30 Correct 20 ms 19676 KB Output is correct
31 Correct 20 ms 19596 KB Output is correct
32 Correct 20 ms 19496 KB Output is correct
33 Correct 111 ms 81356 KB Output is correct
34 Correct 101 ms 81340 KB Output is correct
35 Correct 99 ms 81348 KB Output is correct
36 Correct 104 ms 81392 KB Output is correct
37 Correct 241 ms 85100 KB Output is correct
38 Correct 242 ms 85044 KB Output is correct
39 Correct 240 ms 85136 KB Output is correct
40 Correct 233 ms 81416 KB Output is correct
41 Correct 116 ms 81432 KB Output is correct
42 Correct 119 ms 81732 KB Output is correct
43 Correct 143 ms 82660 KB Output is correct
44 Correct 159 ms 82724 KB Output is correct
45 Correct 83 ms 58264 KB Output is correct
46 Correct 82 ms 55440 KB Output is correct
47 Correct 160 ms 83140 KB Output is correct
48 Correct 183 ms 83120 KB Output is correct
49 Correct 77 ms 101060 KB Output is correct
50 Correct 62 ms 85900 KB Output is correct
51 Correct 73 ms 101072 KB Output is correct
52 Correct 1 ms 460 KB Output is correct
53 Correct 73 ms 101060 KB Output is correct
54 Correct 73 ms 101096 KB Output is correct
55 Correct 76 ms 101024 KB Output is correct
56 Correct 89 ms 101060 KB Output is correct
57 Correct 78 ms 101088 KB Output is correct
58 Correct 72 ms 100684 KB Output is correct
59 Correct 76 ms 100880 KB Output is correct
60 Correct 1 ms 1100 KB Output is correct
61 Correct 694 ms 301516 KB Output is correct
62 Correct 1361 ms 526380 KB Output is correct
63 Correct 1318 ms 528308 KB Output is correct
64 Correct 1310 ms 528408 KB Output is correct
65 Correct 516 ms 310800 KB Output is correct
66 Correct 987 ms 514160 KB Output is correct
67 Correct 1052 ms 525868 KB Output is correct
68 Correct 1 ms 332 KB Output is correct
69 Correct 1 ms 460 KB Output is correct
70 Correct 2 ms 2892 KB Output is correct
71 Correct 2 ms 2380 KB Output is correct
72 Correct 1 ms 844 KB Output is correct
73 Correct 1189 ms 525964 KB Output is correct
74 Correct 1174 ms 526100 KB Output is correct
75 Correct 1188 ms 525960 KB Output is correct
76 Correct 1199 ms 525968 KB Output is correct
77 Correct 3426 ms 574920 KB Output is correct
78 Correct 1151 ms 361788 KB Output is correct
79 Correct 1233 ms 394592 KB Output is correct
80 Correct 2005 ms 542728 KB Output is correct
81 Correct 1219 ms 361912 KB Output is correct
82 Correct 1612 ms 482252 KB Output is correct
83 Correct 2053 ms 542940 KB Output is correct
84 Correct 1359 ms 366512 KB Output is correct
85 Correct 2180 ms 549700 KB Output is correct
86 Correct 2185 ms 538812 KB Output is correct
87 Correct 2037 ms 401072 KB Output is correct
88 Correct 3309 ms 574484 KB Output is correct
89 Correct 3462 ms 574944 KB Output is correct
90 Correct 3427 ms 574828 KB Output is correct