oj.uz

Submission #1034456

# Submission time Handle Problem Language Result Execution time Memory
1034456 2024-07-25T13:58:06 Z amirhoseinfar1385 Rectangles (IOI19_rect) C++17
59 / 100
 1121 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][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][j].begin(),addy[i][j].end());
			sort(allq[i][j].begin(),allq[i][j].end());
	//		cout<<i<<" "<<j<<" :"<<endl;
	//		for(auto x:addy[i][j]){
	//			cout<<x.first<<" "<<x.second<<endl;
	//		}
	//		for(auto x:allq[i][j]){
	//			cout<<x.first<<" "<<x.second.first<<" "<<x.second.second<<endl;
	//		}
			while((int)addy[i][j].size()>0&&(int)allq[i][j].size()>0){
				if(addy[i][j].back().first>=allq[i][j].back().first){
					fen.add(addy[i][j].back().second,1);
					addy[i][j].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][j].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][j].clear();
			allq[i][j].clear();
			addy[i][j].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

# Verdict Execution time Memory Grader output
1 Correct 221 ms 592172 KB Output is correct
2 Correct 226 ms 592424 KB Output is correct
3 Correct 226 ms 592464 KB Output is correct
4 Correct 221 ms 592468 KB Output is correct
5 Correct 222 ms 592208 KB Output is correct
6 Correct 227 ms 592468 KB Output is correct
7 Correct 220 ms 592468 KB Output is correct
8 Correct 221 ms 592212 KB Output is correct
9 Correct 223 ms 592464 KB Output is correct
10 Correct 216 ms 592548 KB Output is correct
11 Correct 234 ms 592356 KB Output is correct
12 Correct 230 ms 592464 KB Output is correct
13 Correct 220 ms 592208 KB Output is correct
14 Correct 214 ms 592212 KB Output is correct
15 Correct 228 ms 592228 KB Output is correct
16 Correct 249 ms 592208 KB Output is correct
17 Correct 229 ms 592096 KB Output is correct
18 Correct 223 ms 592220 KB Output is correct
19 Correct 226 ms 592464 KB Output is correct
20 Correct 225 ms 592292 KB Output is correct
21 Correct 221 ms 592208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 592172 KB Output is correct
2 Correct 226 ms 592424 KB Output is correct
3 Correct 226 ms 592464 KB Output is correct
4 Correct 221 ms 592468 KB Output is correct
5 Correct 222 ms 592208 KB Output is correct
6 Correct 227 ms 592468 KB Output is correct
7 Correct 220 ms 592468 KB Output is correct
8 Correct 221 ms 592212 KB Output is correct
9 Correct 223 ms 592464 KB Output is correct
10 Correct 216 ms 592548 KB Output is correct
11 Correct 234 ms 592356 KB Output is correct
12 Correct 230 ms 592464 KB Output is correct
13 Correct 220 ms 592208 KB Output is correct
14 Correct 214 ms 592212 KB Output is correct
15 Correct 228 ms 592228 KB Output is correct
16 Correct 249 ms 592208 KB Output is correct
17 Correct 229 ms 592096 KB Output is correct
18 Correct 223 ms 592220 KB Output is correct
19 Correct 226 ms 592464 KB Output is correct
20 Correct 225 ms 592292 KB Output is correct
21 Correct 221 ms 592208 KB Output is correct
22 Correct 224 ms 593488 KB Output is correct
23 Correct 237 ms 593424 KB Output is correct
24 Correct 281 ms 593520 KB Output is correct
25 Correct 216 ms 593232 KB Output is correct
26 Correct 217 ms 593376 KB Output is correct
27 Correct 226 ms 593488 KB Output is correct
28 Correct 227 ms 593428 KB Output is correct
29 Correct 240 ms 592988 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 592172 KB Output is correct
2 Correct 226 ms 592424 KB Output is correct
3 Correct 226 ms 592464 KB Output is correct
4 Correct 221 ms 592468 KB Output is correct
5 Correct 222 ms 592208 KB Output is correct
6 Correct 227 ms 592468 KB Output is correct
7 Correct 220 ms 592468 KB Output is correct
8 Correct 221 ms 592212 KB Output is correct
9 Correct 223 ms 592464 KB Output is correct
10 Correct 216 ms 592548 KB Output is correct
11 Correct 234 ms 592356 KB Output is correct
12 Correct 230 ms 592464 KB Output is correct
13 Correct 220 ms 592208 KB Output is correct
14 Correct 214 ms 592212 KB Output is correct
15 Correct 228 ms 592228 KB Output is correct
16 Correct 249 ms 592208 KB Output is correct
17 Correct 224 ms 593488 KB Output is correct
18 Correct 237 ms 593424 KB Output is correct
19 Correct 281 ms 593520 KB Output is correct
20 Correct 216 ms 593232 KB Output is correct
21 Correct 217 ms 593376 KB Output is correct
22 Correct 226 ms 593488 KB Output is correct
23 Correct 227 ms 593428 KB Output is correct
24 Correct 240 ms 592988 KB Output is correct
25 Correct 229 ms 592096 KB Output is correct
26 Correct 223 ms 592220 KB Output is correct
27 Correct 226 ms 592464 KB Output is correct
28 Correct 225 ms 592292 KB Output is correct
29 Correct 221 ms 592208 KB Output is correct
30 Correct 229 ms 598604 KB Output is correct
31 Correct 252 ms 598724 KB Output is correct
32 Correct 225 ms 598552 KB Output is correct
33 Correct 217 ms 597348 KB Output is correct
34 Correct 223 ms 598264 KB Output is correct
35 Correct 226 ms 597992 KB Output is correct
36 Correct 211 ms 597856 KB Output is correct
37 Correct 237 ms 597844 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 592172 KB Output is correct
2 Correct 226 ms 592424 KB Output is correct
3 Correct 226 ms 592464 KB Output is correct
4 Correct 221 ms 592468 KB Output is correct
5 Correct 222 ms 592208 KB Output is correct
6 Correct 227 ms 592468 KB Output is correct
7 Correct 220 ms 592468 KB Output is correct
8 Correct 221 ms 592212 KB Output is correct
9 Correct 223 ms 592464 KB Output is correct
10 Correct 216 ms 592548 KB Output is correct
11 Correct 234 ms 592356 KB Output is correct
12 Correct 230 ms 592464 KB Output is correct
13 Correct 220 ms 592208 KB Output is correct
14 Correct 214 ms 592212 KB Output is correct
15 Correct 228 ms 592228 KB Output is correct
16 Correct 249 ms 592208 KB Output is correct
17 Correct 224 ms 593488 KB Output is correct
18 Correct 237 ms 593424 KB Output is correct
19 Correct 281 ms 593520 KB Output is correct
20 Correct 216 ms 593232 KB Output is correct
21 Correct 217 ms 593376 KB Output is correct
22 Correct 226 ms 593488 KB Output is correct
23 Correct 227 ms 593428 KB Output is correct
24 Correct 240 ms 592988 KB Output is correct
25 Correct 229 ms 598604 KB Output is correct
26 Correct 252 ms 598724 KB Output is correct
27 Correct 225 ms 598552 KB Output is correct
28 Correct 217 ms 597348 KB Output is correct
29 Correct 223 ms 598264 KB Output is correct
30 Correct 226 ms 597992 KB Output is correct
31 Correct 211 ms 597856 KB Output is correct
32 Correct 237 ms 597844 KB Output is correct
33 Correct 229 ms 592096 KB Output is correct
34 Correct 223 ms 592220 KB Output is correct
35 Correct 226 ms 592464 KB Output is correct
36 Correct 225 ms 592292 KB Output is correct
37 Correct 221 ms 592208 KB Output is correct
38 Correct 320 ms 647252 KB Output is correct
39 Correct 377 ms 644692 KB Output is correct
40 Correct 302 ms 644704 KB Output is correct
41 Correct 323 ms 642264 KB Output is correct
42 Correct 358 ms 656972 KB Output is correct
43 Correct 407 ms 656864 KB Output is correct
44 Correct 353 ms 657232 KB Output is correct
45 Correct 344 ms 653136 KB Output is correct
46 Correct 346 ms 640852 KB Output is correct
47 Correct 386 ms 642220 KB Output is correct
48 Correct 431 ms 647520 KB Output is correct
49 Correct 443 ms 649260 KB Output is correct
50 Correct 321 ms 623616 KB Output is correct
51 Correct 304 ms 620880 KB Output is correct
52 Correct 423 ms 647760 KB Output is correct
53 Correct 429 ms 649044 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 592720 KB Output is correct
2 Correct 222 ms 592724 KB Output is correct
3 Correct 220 ms 592720 KB Output is correct
4 Correct 225 ms 592212 KB Output is correct
5 Correct 217 ms 592724 KB Output is correct
6 Correct 213 ms 592724 KB Output is correct
7 Correct 249 ms 592724 KB Output is correct
8 Correct 237 ms 592696 KB Output is correct
9 Correct 223 ms 592724 KB Output is correct
10 Correct 238 ms 592244 KB Output is correct
11 Correct 227 ms 592464 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 592096 KB Output is correct
2 Correct 223 ms 592220 KB Output is correct
3 Correct 226 ms 592464 KB Output is correct
4 Correct 225 ms 592292 KB Output is correct
5 Correct 221 ms 592208 KB Output is correct
6 Correct 237 ms 592144 KB Output is correct
7 Correct 1121 ms 846200 KB Output is correct
8 Runtime error 765 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 592172 KB Output is correct
2 Correct 226 ms 592424 KB Output is correct
3 Correct 226 ms 592464 KB Output is correct
4 Correct 221 ms 592468 KB Output is correct
5 Correct 222 ms 592208 KB Output is correct
6 Correct 227 ms 592468 KB Output is correct
7 Correct 220 ms 592468 KB Output is correct
8 Correct 221 ms 592212 KB Output is correct
9 Correct 223 ms 592464 KB Output is correct
10 Correct 216 ms 592548 KB Output is correct
11 Correct 234 ms 592356 KB Output is correct
12 Correct 230 ms 592464 KB Output is correct
13 Correct 220 ms 592208 KB Output is correct
14 Correct 214 ms 592212 KB Output is correct
15 Correct 228 ms 592228 KB Output is correct
16 Correct 249 ms 592208 KB Output is correct
17 Correct 224 ms 593488 KB Output is correct
18 Correct 237 ms 593424 KB Output is correct
19 Correct 281 ms 593520 KB Output is correct
20 Correct 216 ms 593232 KB Output is correct
21 Correct 217 ms 593376 KB Output is correct
22 Correct 226 ms 593488 KB Output is correct
23 Correct 227 ms 593428 KB Output is correct
24 Correct 240 ms 592988 KB Output is correct
25 Correct 229 ms 598604 KB Output is correct
26 Correct 252 ms 598724 KB Output is correct
27 Correct 225 ms 598552 KB Output is correct
28 Correct 217 ms 597348 KB Output is correct
29 Correct 223 ms 598264 KB Output is correct
30 Correct 226 ms 597992 KB Output is correct
31 Correct 211 ms 597856 KB Output is correct
32 Correct 237 ms 597844 KB Output is correct
33 Correct 320 ms 647252 KB Output is correct
34 Correct 377 ms 644692 KB Output is correct
35 Correct 302 ms 644704 KB Output is correct
36 Correct 323 ms 642264 KB Output is correct
37 Correct 358 ms 656972 KB Output is correct
38 Correct 407 ms 656864 KB Output is correct
39 Correct 353 ms 657232 KB Output is correct
40 Correct 344 ms 653136 KB Output is correct
41 Correct 346 ms 640852 KB Output is correct
42 Correct 386 ms 642220 KB Output is correct
43 Correct 431 ms 647520 KB Output is correct
44 Correct 443 ms 649260 KB Output is correct
45 Correct 321 ms 623616 KB Output is correct
46 Correct 304 ms 620880 KB Output is correct
47 Correct 423 ms 647760 KB Output is correct
48 Correct 429 ms 649044 KB Output is correct
49 Correct 231 ms 592720 KB Output is correct
50 Correct 222 ms 592724 KB Output is correct
51 Correct 220 ms 592720 KB Output is correct
52 Correct 225 ms 592212 KB Output is correct
53 Correct 217 ms 592724 KB Output is correct
54 Correct 213 ms 592724 KB Output is correct
55 Correct 249 ms 592724 KB Output is correct
56 Correct 237 ms 592696 KB Output is correct
57 Correct 223 ms 592724 KB Output is correct
58 Correct 238 ms 592244 KB Output is correct
59 Correct 227 ms 592464 KB Output is correct
60 Correct 237 ms 592144 KB Output is correct
61 Correct 1121 ms 846200 KB Output is correct
62 Runtime error 765 ms 1048576 KB Execution killed with signal 9
63 Halted 0 ms 0 KB -