oj.uz

답안 #1034882

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1034882 2024-07-25T20:42:24 Z amirhoseinfar1385 Rectangles (IOI19_rect) C++17
72 / 100
 1954 ms 1048576 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2500+10;
int all[maxn][maxn],vis[maxn][maxn],tp[maxn][maxn],n,m,dpp[maxn][maxn];
vector<int>alll[maxn][maxn],alld[maxn][maxn];
vector<pair<int,int>>allq[maxn][maxn];
vector<pair<int,int>>addy[maxn];
long long mainres=0;

struct fenwick{
	int fn[maxn];
	vector<int>allind;
	void clear(){
		for(auto x:allind){
			while(x<maxn){
				fn[x]=0;
				x+=((-x)&x);
			}
		}
		allind.shrink_to_fit();
		allind.clear();
	}
	void add(int i,int w){
		i++;
		allind.push_back(i);
		while(i<maxn){
			fn[i]+=w;
			i+=((-i)&i);
		}
	}
	int pors(int l,int r){
		int ret=0;
		r++;
		while(l>0){
			ret-=fn[l];
			l-=((-l)&l);
		}
		while(r>0){
			ret+=fn[r];
			r-=((-r)&r);
		}
		return ret;
	}
}fen;


void pre(){
	for(int i=1;i<=n;i++){
		vector<pair<int,int>>allv;
		for(int j=1;j<=m;j++){
			while((int)allv.size()>0&&allv.back().first<all[i][j]){
				alll[i][j].push_back(allv.back().second);
				allv.pop_back();
			}
			if((int)allv.size()>0){
				alll[i][j].push_back(allv.back().second);
			}
			if((int)allv.size()>0&&allv.back().first==all[i][j]){
				allv.pop_back();
			}
			allv.push_back(make_pair(all[i][j],j));
		}
	}
	for(int j=1;j<=m;j++){
		vector<pair<int,int>>allv;
		for(int i=n;i>=1;i--){
			while((int)allv.size()>0&&allv.back().first<all[i][j]){
				alld[i][j].push_back(allv.back().second);
				allv.pop_back();
			}
			if((int)allv.size()>0){
				alld[i][j].push_back(allv.back().second);
			}
			if((int)allv.size()>0&&allv.back().first==all[i][j]){
				allv.pop_back();
			}
			allv.push_back(make_pair(all[i][j],i));
		}
	}
}

void solveq(int i,int j){
			sort(addy[i].begin(),addy[i].end());
			sort(allq[i][j].begin(),allq[i][j].end());
			while((int)addy[i].size()>0&&(int)allq[i][j].size()>0){
				if(addy[i].back().first>=allq[i][j].back().first){
					fen.add(addy[i].back().second,1);
					addy[i].pop_back();
				}else{
					mainres+=fen.pors(allq[i][j].back().second,j-2);
					allq[i][j].pop_back();
				}
			}
			while((int)allq[i][j].size()>0){
				mainres+=fen.pors(allq[i][j].back().second,j-2);
				allq[i][j].pop_back();
			}
			fen.clear();
}

void calq(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(auto x:alld[i][j]){
				if(x<=i+1){
					continue;
				}
				dpp[x][j]=dpp[x][j-1]+1;
				allq[i+1][j+1].push_back(make_pair((x-i-1),j-dpp[x][j]));
			}
		}
		for(int j=1;j<=m;j++){
			for(auto x:alld[i][j]){
				if(x<=i+1){
					continue;
				}
				dpp[x][j]=0;
			}
		}
	}
	for(int j=1;j<=m;j++){
		for(int i=n;i>=1;i--){
			for(auto x:alll[i][j]){
				if(x+1>=j){
					continue;
				}
				dpp[i][x]=dpp[i+1][x]+1;
				addy[i].push_back(make_pair(dpp[i][x],x));
			}
			solveq(i,j);
		}
		for(int i=n;i>=1;i--){
			for(auto x:alll[i][j]){
				if(x+1>=j){
					continue;
				}
				dpp[i][x]=0;
			}
			addy[i].clear();
			allq[i][j].clear();
			addy[i].shrink_to_fit();
			allq[i][j].shrink_to_fit();
		}
	}
}

void solve(){
	pre();
	calq();
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	n=a.size();
	m=a[0].size();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			all[i][j]=a[i-1][j-1];
		}
	}
	solve();
	return mainres;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 444240 KB Output is correct
2 Correct 167 ms 444496 KB Output is correct
3 Correct 167 ms 444500 KB Output is correct
4 Correct 159 ms 444656 KB Output is correct
5 Correct 161 ms 444424 KB Output is correct
6 Correct 159 ms 444580 KB Output is correct
7 Correct 162 ms 444500 KB Output is correct
8 Correct 162 ms 444240 KB Output is correct
9 Correct 165 ms 444496 KB Output is correct
10 Correct 163 ms 444496 KB Output is correct
11 Correct 171 ms 444496 KB Output is correct
12 Correct 163 ms 444500 KB Output is correct
13 Correct 169 ms 444240 KB Output is correct
14 Correct 161 ms 444240 KB Output is correct
15 Correct 156 ms 444244 KB Output is correct
16 Correct 158 ms 444216 KB Output is correct
17 Correct 159 ms 444240 KB Output is correct
18 Correct 154 ms 444244 KB Output is correct
19 Correct 153 ms 444496 KB Output is correct
20 Correct 167 ms 444356 KB Output is correct
21 Correct 156 ms 444340 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 444240 KB Output is correct
2 Correct 167 ms 444496 KB Output is correct
3 Correct 167 ms 444500 KB Output is correct
4 Correct 159 ms 444656 KB Output is correct
5 Correct 161 ms 444424 KB Output is correct
6 Correct 159 ms 444580 KB Output is correct
7 Correct 162 ms 444500 KB Output is correct
8 Correct 162 ms 444240 KB Output is correct
9 Correct 165 ms 444496 KB Output is correct
10 Correct 163 ms 444496 KB Output is correct
11 Correct 171 ms 444496 KB Output is correct
12 Correct 163 ms 444500 KB Output is correct
13 Correct 169 ms 444240 KB Output is correct
14 Correct 161 ms 444240 KB Output is correct
15 Correct 156 ms 444244 KB Output is correct
16 Correct 158 ms 444216 KB Output is correct
17 Correct 159 ms 444240 KB Output is correct
18 Correct 154 ms 444244 KB Output is correct
19 Correct 153 ms 444496 KB Output is correct
20 Correct 167 ms 444356 KB Output is correct
21 Correct 156 ms 444340 KB Output is correct
22 Correct 165 ms 445640 KB Output is correct
23 Correct 160 ms 445612 KB Output is correct
24 Correct 164 ms 445524 KB Output is correct
25 Correct 163 ms 445400 KB Output is correct
26 Correct 168 ms 445520 KB Output is correct
27 Correct 174 ms 445520 KB Output is correct
28 Correct 167 ms 445524 KB Output is correct
29 Correct 167 ms 445088 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 444240 KB Output is correct
2 Correct 167 ms 444496 KB Output is correct
3 Correct 167 ms 444500 KB Output is correct
4 Correct 159 ms 444656 KB Output is correct
5 Correct 161 ms 444424 KB Output is correct
6 Correct 159 ms 444580 KB Output is correct
7 Correct 162 ms 444500 KB Output is correct
8 Correct 162 ms 444240 KB Output is correct
9 Correct 165 ms 444496 KB Output is correct
10 Correct 163 ms 444496 KB Output is correct
11 Correct 171 ms 444496 KB Output is correct
12 Correct 163 ms 444500 KB Output is correct
13 Correct 169 ms 444240 KB Output is correct
14 Correct 161 ms 444240 KB Output is correct
15 Correct 156 ms 444244 KB Output is correct
16 Correct 158 ms 444216 KB Output is correct
17 Correct 165 ms 445640 KB Output is correct
18 Correct 160 ms 445612 KB Output is correct
19 Correct 164 ms 445524 KB Output is correct
20 Correct 163 ms 445400 KB Output is correct
21 Correct 168 ms 445520 KB Output is correct
22 Correct 174 ms 445520 KB Output is correct
23 Correct 167 ms 445524 KB Output is correct
24 Correct 167 ms 445088 KB Output is correct
25 Correct 159 ms 444240 KB Output is correct
26 Correct 154 ms 444244 KB Output is correct
27 Correct 153 ms 444496 KB Output is correct
28 Correct 167 ms 444356 KB Output is correct
29 Correct 156 ms 444340 KB Output is correct
30 Correct 171 ms 450644 KB Output is correct
31 Correct 207 ms 450524 KB Output is correct
32 Correct 198 ms 450716 KB Output is correct
33 Correct 174 ms 449364 KB Output is correct
34 Correct 176 ms 449868 KB Output is correct
35 Correct 178 ms 450084 KB Output is correct
36 Correct 178 ms 450068 KB Output is correct
37 Correct 180 ms 450036 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 444240 KB Output is correct
2 Correct 167 ms 444496 KB Output is correct
3 Correct 167 ms 444500 KB Output is correct
4 Correct 159 ms 444656 KB Output is correct
5 Correct 161 ms 444424 KB Output is correct
6 Correct 159 ms 444580 KB Output is correct
7 Correct 162 ms 444500 KB Output is correct
8 Correct 162 ms 444240 KB Output is correct
9 Correct 165 ms 444496 KB Output is correct
10 Correct 163 ms 444496 KB Output is correct
11 Correct 171 ms 444496 KB Output is correct
12 Correct 163 ms 444500 KB Output is correct
13 Correct 169 ms 444240 KB Output is correct
14 Correct 161 ms 444240 KB Output is correct
15 Correct 156 ms 444244 KB Output is correct
16 Correct 158 ms 444216 KB Output is correct
17 Correct 165 ms 445640 KB Output is correct
18 Correct 160 ms 445612 KB Output is correct
19 Correct 164 ms 445524 KB Output is correct
20 Correct 163 ms 445400 KB Output is correct
21 Correct 168 ms 445520 KB Output is correct
22 Correct 174 ms 445520 KB Output is correct
23 Correct 167 ms 445524 KB Output is correct
24 Correct 167 ms 445088 KB Output is correct
25 Correct 171 ms 450644 KB Output is correct
26 Correct 207 ms 450524 KB Output is correct
27 Correct 198 ms 450716 KB Output is correct
28 Correct 174 ms 449364 KB Output is correct
29 Correct 176 ms 449868 KB Output is correct
30 Correct 178 ms 450084 KB Output is correct
31 Correct 178 ms 450068 KB Output is correct
32 Correct 180 ms 450036 KB Output is correct
33 Correct 159 ms 444240 KB Output is correct
34 Correct 154 ms 444244 KB Output is correct
35 Correct 153 ms 444496 KB Output is correct
36 Correct 167 ms 444356 KB Output is correct
37 Correct 156 ms 444340 KB Output is correct
38 Correct 272 ms 499384 KB Output is correct
39 Correct 270 ms 496980 KB Output is correct
40 Correct 254 ms 497020 KB Output is correct
41 Correct 248 ms 494676 KB Output is correct
42 Correct 371 ms 509524 KB Output is correct
43 Correct 285 ms 509520 KB Output is correct
44 Correct 299 ms 509776 KB Output is correct
45 Correct 275 ms 505656 KB Output is correct
46 Correct 266 ms 492880 KB Output is correct
47 Correct 288 ms 494164 KB Output is correct
48 Correct 369 ms 499796 KB Output is correct
49 Correct 382 ms 502028 KB Output is correct
50 Correct 265 ms 475872 KB Output is correct
51 Correct 266 ms 473168 KB Output is correct
52 Correct 347 ms 500048 KB Output is correct
53 Correct 348 ms 501200 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 445016 KB Output is correct
2 Correct 158 ms 444904 KB Output is correct
3 Correct 172 ms 444752 KB Output is correct
4 Correct 167 ms 444240 KB Output is correct
5 Correct 165 ms 444760 KB Output is correct
6 Correct 172 ms 444756 KB Output is correct
7 Correct 171 ms 444916 KB Output is correct
8 Correct 167 ms 444752 KB Output is correct
9 Correct 164 ms 444788 KB Output is correct
10 Correct 164 ms 444240 KB Output is correct
11 Correct 161 ms 444496 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 444240 KB Output is correct
2 Correct 154 ms 444244 KB Output is correct
3 Correct 153 ms 444496 KB Output is correct
4 Correct 167 ms 444356 KB Output is correct
5 Correct 156 ms 444340 KB Output is correct
6 Correct 165 ms 444240 KB Output is correct
7 Correct 932 ms 698104 KB Output is correct
8 Correct 1952 ms 992008 KB Output is correct
9 Correct 1813 ms 994564 KB Output is correct
10 Correct 1831 ms 994776 KB Output is correct
11 Correct 582 ms 679764 KB Output is correct
12 Correct 1042 ms 893172 KB Output is correct
13 Correct 1047 ms 921224 KB Output is correct

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 444240 KB Output is correct
2 Correct 167 ms 444496 KB Output is correct
3 Correct 167 ms 444500 KB Output is correct
4 Correct 159 ms 444656 KB Output is correct
5 Correct 161 ms 444424 KB Output is correct
6 Correct 159 ms 444580 KB Output is correct
7 Correct 162 ms 444500 KB Output is correct
8 Correct 162 ms 444240 KB Output is correct
9 Correct 165 ms 444496 KB Output is correct
10 Correct 163 ms 444496 KB Output is correct
11 Correct 171 ms 444496 KB Output is correct
12 Correct 163 ms 444500 KB Output is correct
13 Correct 169 ms 444240 KB Output is correct
14 Correct 161 ms 444240 KB Output is correct
15 Correct 156 ms 444244 KB Output is correct
16 Correct 158 ms 444216 KB Output is correct
17 Correct 165 ms 445640 KB Output is correct
18 Correct 160 ms 445612 KB Output is correct
19 Correct 164 ms 445524 KB Output is correct
20 Correct 163 ms 445400 KB Output is correct
21 Correct 168 ms 445520 KB Output is correct
22 Correct 174 ms 445520 KB Output is correct
23 Correct 167 ms 445524 KB Output is correct
24 Correct 167 ms 445088 KB Output is correct
25 Correct 171 ms 450644 KB Output is correct
26 Correct 207 ms 450524 KB Output is correct
27 Correct 198 ms 450716 KB Output is correct
28 Correct 174 ms 449364 KB Output is correct
29 Correct 176 ms 449868 KB Output is correct
30 Correct 178 ms 450084 KB Output is correct
31 Correct 178 ms 450068 KB Output is correct
32 Correct 180 ms 450036 KB Output is correct
33 Correct 272 ms 499384 KB Output is correct
34 Correct 270 ms 496980 KB Output is correct
35 Correct 254 ms 497020 KB Output is correct
36 Correct 248 ms 494676 KB Output is correct
37 Correct 371 ms 509524 KB Output is correct
38 Correct 285 ms 509520 KB Output is correct
39 Correct 299 ms 509776 KB Output is correct
40 Correct 275 ms 505656 KB Output is correct
41 Correct 266 ms 492880 KB Output is correct
42 Correct 288 ms 494164 KB Output is correct
43 Correct 369 ms 499796 KB Output is correct
44 Correct 382 ms 502028 KB Output is correct
45 Correct 265 ms 475872 KB Output is correct
46 Correct 266 ms 473168 KB Output is correct
47 Correct 347 ms 500048 KB Output is correct
48 Correct 348 ms 501200 KB Output is correct
49 Correct 160 ms 445016 KB Output is correct
50 Correct 158 ms 444904 KB Output is correct
51 Correct 172 ms 444752 KB Output is correct
52 Correct 167 ms 444240 KB Output is correct
53 Correct 165 ms 444760 KB Output is correct
54 Correct 172 ms 444756 KB Output is correct
55 Correct 171 ms 444916 KB Output is correct
56 Correct 167 ms 444752 KB Output is correct
57 Correct 164 ms 444788 KB Output is correct
58 Correct 164 ms 444240 KB Output is correct
59 Correct 161 ms 444496 KB Output is correct
60 Correct 165 ms 444240 KB Output is correct
61 Correct 932 ms 698104 KB Output is correct
62 Correct 1952 ms 992008 KB Output is correct
63 Correct 1813 ms 994564 KB Output is correct
64 Correct 1831 ms 994776 KB Output is correct
65 Correct 582 ms 679764 KB Output is correct
66 Correct 1042 ms 893172 KB Output is correct
67 Correct 1047 ms 921224 KB Output is correct
68 Correct 159 ms 444240 KB Output is correct
69 Correct 154 ms 444244 KB Output is correct
70 Correct 153 ms 444496 KB Output is correct
71 Correct 167 ms 444356 KB Output is correct
72 Correct 156 ms 444340 KB Output is correct
73 Correct 1756 ms 1048576 KB Output is correct
74 Correct 1954 ms 1048576 KB Output is correct
75 Correct 1390 ms 1044816 KB Output is correct
76 Correct 1428 ms 1023624 KB Output is correct
77 Runtime error 952 ms 1048576 KB Execution killed with signal 9
78 Halted 0 ms 0 KB -