oj.uz

Submission #1034438

# Submission time Handle Problem Language Result Execution time Memory
1034438 2024-07-25T13:50:12 Z amirhoseinfar1385 Rectangles (IOI19_rect) C++17
59 / 100
 1059 ms 1048576 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=2500+100;
long long all[maxn][maxn],vis[maxn][maxn],tp[maxn][maxn],n,m,dpp[maxn][maxn],dpd[maxn][maxn];
vector<long long>alll[maxn][maxn],alld[maxn][maxn];
vector<pair<long long,pair<long long,long long>>>allq[maxn][maxn];
vector<pair<long long,long long>>addy[maxn][maxn];
long long mainres=0;

struct fenwick{
	long long fn[maxn];
	vector<long long>allind;
	void clear(){
		for(auto x:allind){
			while(x<maxn){
				fn[x]=0;
				x+=((-x)&x);
			}
		}
		allind.clear();
	}
	void add(long long i,long long w){
		i++;
		allind.push_back(i);
		while(i<maxn){
			fn[i]+=w;
			i+=((-i)&i);
		}
	}
	long long pors(long long l,long long r){
		long long 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(long long i=1;i<=n;i++){
		vector<pair<long long,long long>>allv;
		for(long long j=1;j<=m;j++){
			while((long long)allv.size()>0&&allv.back().first<all[i][j]){
				alll[i][j].push_back(allv.back().second);
				allv.pop_back();
			}
			if((long long)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(long long j=1;j<=m;j++){
		vector<pair<long long,long long>>allv;
		for(long long i=n;i>=1;i--){
			while((long long)allv.size()>0&&allv.back().first<all[i][j]){
				alld[i][j].push_back(allv.back().second);
				allv.pop_back();
			}
			if((long long)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(){
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;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((long long)addy[i][j].size()>0&&(long long)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.first,allq[i][j].back().second.second);
					allq[i][j].pop_back();
				}
			}
			while((long long)allq[i][j].size()>0){
				mainres+=fen.pors(allq[i][j].back().second.first,allq[i][j].back().second.second);
				allq[i][j].pop_back();
			}
			fen.clear();
		}
	}
}

void calq(){
	for(long long i=1;i<=n;i++){
		for(long long 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),make_pair(j-dpp[x][j],j-1)));
			}
		}
		for(long long j=1;j<=m;j++){
			for(auto x:alld[i][j]){
				if(x<=i+1){
					continue;
				}
				dpp[x][j]=0;
			}
		}
	}
	for(long long j=1;j<=m;j++){
		for(long long 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));
			}
		}
		for(long long i=n;i>=1;i--){
			for(auto x:alll[i][j]){
				if(x+1>=j){
					continue;
				}
				dpp[i][x]=0;
			}
		}
	}
}

void solve(){
	pre();
	calq();
	solveq();
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	n=a.size();
	m=a[0].size();
	for(long long i=1;i<=n;i++){
		for(long long 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 254 ms 635728 KB Output is correct
2 Correct 264 ms 635732 KB Output is correct
3 Correct 235 ms 635732 KB Output is correct
4 Correct 242 ms 635728 KB Output is correct
5 Correct 226 ms 635476 KB Output is correct
6 Correct 285 ms 635724 KB Output is correct
7 Correct 229 ms 635732 KB Output is correct
8 Correct 219 ms 635620 KB Output is correct
9 Correct 259 ms 635732 KB Output is correct
10 Correct 228 ms 635728 KB Output is correct
11 Correct 236 ms 635732 KB Output is correct
12 Correct 233 ms 635732 KB Output is correct
13 Correct 241 ms 635220 KB Output is correct
14 Correct 278 ms 635312 KB Output is correct
15 Correct 237 ms 635380 KB Output is correct
16 Correct 235 ms 635220 KB Output is correct
17 Correct 233 ms 635216 KB Output is correct
18 Correct 230 ms 635180 KB Output is correct
19 Correct 226 ms 635728 KB Output is correct
20 Correct 234 ms 635436 KB Output is correct
21 Correct 233 ms 635220 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 635728 KB Output is correct
2 Correct 264 ms 635732 KB Output is correct
3 Correct 235 ms 635732 KB Output is correct
4 Correct 242 ms 635728 KB Output is correct
5 Correct 226 ms 635476 KB Output is correct
6 Correct 285 ms 635724 KB Output is correct
7 Correct 229 ms 635732 KB Output is correct
8 Correct 219 ms 635620 KB Output is correct
9 Correct 259 ms 635732 KB Output is correct
10 Correct 228 ms 635728 KB Output is correct
11 Correct 236 ms 635732 KB Output is correct
12 Correct 233 ms 635732 KB Output is correct
13 Correct 241 ms 635220 KB Output is correct
14 Correct 278 ms 635312 KB Output is correct
15 Correct 237 ms 635380 KB Output is correct
16 Correct 235 ms 635220 KB Output is correct
17 Correct 233 ms 635216 KB Output is correct
18 Correct 230 ms 635180 KB Output is correct
19 Correct 226 ms 635728 KB Output is correct
20 Correct 234 ms 635436 KB Output is correct
21 Correct 233 ms 635220 KB Output is correct
22 Correct 244 ms 636952 KB Output is correct
23 Correct 245 ms 637016 KB Output is correct
24 Correct 222 ms 637024 KB Output is correct
25 Correct 241 ms 636736 KB Output is correct
26 Correct 235 ms 636756 KB Output is correct
27 Correct 226 ms 637004 KB Output is correct
28 Correct 226 ms 636788 KB Output is correct
29 Correct 236 ms 636472 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 635728 KB Output is correct
2 Correct 264 ms 635732 KB Output is correct
3 Correct 235 ms 635732 KB Output is correct
4 Correct 242 ms 635728 KB Output is correct
5 Correct 226 ms 635476 KB Output is correct
6 Correct 285 ms 635724 KB Output is correct
7 Correct 229 ms 635732 KB Output is correct
8 Correct 219 ms 635620 KB Output is correct
9 Correct 259 ms 635732 KB Output is correct
10 Correct 228 ms 635728 KB Output is correct
11 Correct 236 ms 635732 KB Output is correct
12 Correct 233 ms 635732 KB Output is correct
13 Correct 241 ms 635220 KB Output is correct
14 Correct 278 ms 635312 KB Output is correct
15 Correct 237 ms 635380 KB Output is correct
16 Correct 235 ms 635220 KB Output is correct
17 Correct 244 ms 636952 KB Output is correct
18 Correct 245 ms 637016 KB Output is correct
19 Correct 222 ms 637024 KB Output is correct
20 Correct 241 ms 636736 KB Output is correct
21 Correct 235 ms 636756 KB Output is correct
22 Correct 226 ms 637004 KB Output is correct
23 Correct 226 ms 636788 KB Output is correct
24 Correct 236 ms 636472 KB Output is correct
25 Correct 233 ms 635216 KB Output is correct
26 Correct 230 ms 635180 KB Output is correct
27 Correct 226 ms 635728 KB Output is correct
28 Correct 234 ms 635436 KB Output is correct
29 Correct 233 ms 635220 KB Output is correct
30 Correct 235 ms 642896 KB Output is correct
31 Correct 246 ms 642900 KB Output is correct
32 Correct 228 ms 642732 KB Output is correct
33 Correct 242 ms 641364 KB Output is correct
34 Correct 256 ms 642896 KB Output is correct
35 Correct 257 ms 643152 KB Output is correct
36 Correct 247 ms 642896 KB Output is correct
37 Correct 260 ms 642644 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 635728 KB Output is correct
2 Correct 264 ms 635732 KB Output is correct
3 Correct 235 ms 635732 KB Output is correct
4 Correct 242 ms 635728 KB Output is correct
5 Correct 226 ms 635476 KB Output is correct
6 Correct 285 ms 635724 KB Output is correct
7 Correct 229 ms 635732 KB Output is correct
8 Correct 219 ms 635620 KB Output is correct
9 Correct 259 ms 635732 KB Output is correct
10 Correct 228 ms 635728 KB Output is correct
11 Correct 236 ms 635732 KB Output is correct
12 Correct 233 ms 635732 KB Output is correct
13 Correct 241 ms 635220 KB Output is correct
14 Correct 278 ms 635312 KB Output is correct
15 Correct 237 ms 635380 KB Output is correct
16 Correct 235 ms 635220 KB Output is correct
17 Correct 244 ms 636952 KB Output is correct
18 Correct 245 ms 637016 KB Output is correct
19 Correct 222 ms 637024 KB Output is correct
20 Correct 241 ms 636736 KB Output is correct
21 Correct 235 ms 636756 KB Output is correct
22 Correct 226 ms 637004 KB Output is correct
23 Correct 226 ms 636788 KB Output is correct
24 Correct 236 ms 636472 KB Output is correct
25 Correct 235 ms 642896 KB Output is correct
26 Correct 246 ms 642900 KB Output is correct
27 Correct 228 ms 642732 KB Output is correct
28 Correct 242 ms 641364 KB Output is correct
29 Correct 256 ms 642896 KB Output is correct
30 Correct 257 ms 643152 KB Output is correct
31 Correct 247 ms 642896 KB Output is correct
32 Correct 260 ms 642644 KB Output is correct
33 Correct 233 ms 635216 KB Output is correct
34 Correct 230 ms 635180 KB Output is correct
35 Correct 226 ms 635728 KB Output is correct
36 Correct 234 ms 635436 KB Output is correct
37 Correct 233 ms 635220 KB Output is correct
38 Correct 333 ms 696900 KB Output is correct
39 Correct 322 ms 694612 KB Output is correct
40 Correct 322 ms 701332 KB Output is correct
41 Correct 343 ms 699000 KB Output is correct
42 Correct 332 ms 714576 KB Output is correct
43 Correct 367 ms 714324 KB Output is correct
44 Correct 329 ms 714580 KB Output is correct
45 Correct 392 ms 709348 KB Output is correct
46 Correct 318 ms 690768 KB Output is correct
47 Correct 354 ms 695380 KB Output is correct
48 Correct 409 ms 716616 KB Output is correct
49 Correct 458 ms 717116 KB Output is correct
50 Correct 341 ms 678972 KB Output is correct
51 Correct 325 ms 675924 KB Output is correct
52 Correct 414 ms 714064 KB Output is correct
53 Correct 432 ms 714188 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 636288 KB Output is correct
2 Correct 224 ms 636060 KB Output is correct
3 Correct 241 ms 635728 KB Output is correct
4 Correct 238 ms 635340 KB Output is correct
5 Correct 230 ms 636240 KB Output is correct
6 Correct 234 ms 636044 KB Output is correct
7 Correct 238 ms 636240 KB Output is correct
8 Correct 236 ms 636264 KB Output is correct
9 Correct 243 ms 636240 KB Output is correct
10 Correct 237 ms 635576 KB Output is correct
11 Correct 238 ms 635732 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 635216 KB Output is correct
2 Correct 230 ms 635180 KB Output is correct
3 Correct 226 ms 635728 KB Output is correct
4 Correct 234 ms 635436 KB Output is correct
5 Correct 233 ms 635220 KB Output is correct
6 Correct 239 ms 635280 KB Output is correct
7 Correct 1059 ms 932020 KB Output is correct
8 Runtime error 785 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 254 ms 635728 KB Output is correct
2 Correct 264 ms 635732 KB Output is correct
3 Correct 235 ms 635732 KB Output is correct
4 Correct 242 ms 635728 KB Output is correct
5 Correct 226 ms 635476 KB Output is correct
6 Correct 285 ms 635724 KB Output is correct
7 Correct 229 ms 635732 KB Output is correct
8 Correct 219 ms 635620 KB Output is correct
9 Correct 259 ms 635732 KB Output is correct
10 Correct 228 ms 635728 KB Output is correct
11 Correct 236 ms 635732 KB Output is correct
12 Correct 233 ms 635732 KB Output is correct
13 Correct 241 ms 635220 KB Output is correct
14 Correct 278 ms 635312 KB Output is correct
15 Correct 237 ms 635380 KB Output is correct
16 Correct 235 ms 635220 KB Output is correct
17 Correct 244 ms 636952 KB Output is correct
18 Correct 245 ms 637016 KB Output is correct
19 Correct 222 ms 637024 KB Output is correct
20 Correct 241 ms 636736 KB Output is correct
21 Correct 235 ms 636756 KB Output is correct
22 Correct 226 ms 637004 KB Output is correct
23 Correct 226 ms 636788 KB Output is correct
24 Correct 236 ms 636472 KB Output is correct
25 Correct 235 ms 642896 KB Output is correct
26 Correct 246 ms 642900 KB Output is correct
27 Correct 228 ms 642732 KB Output is correct
28 Correct 242 ms 641364 KB Output is correct
29 Correct 256 ms 642896 KB Output is correct
30 Correct 257 ms 643152 KB Output is correct
31 Correct 247 ms 642896 KB Output is correct
32 Correct 260 ms 642644 KB Output is correct
33 Correct 333 ms 696900 KB Output is correct
34 Correct 322 ms 694612 KB Output is correct
35 Correct 322 ms 701332 KB Output is correct
36 Correct 343 ms 699000 KB Output is correct
37 Correct 332 ms 714576 KB Output is correct
38 Correct 367 ms 714324 KB Output is correct
39 Correct 329 ms 714580 KB Output is correct
40 Correct 392 ms 709348 KB Output is correct
41 Correct 318 ms 690768 KB Output is correct
42 Correct 354 ms 695380 KB Output is correct
43 Correct 409 ms 716616 KB Output is correct
44 Correct 458 ms 717116 KB Output is correct
45 Correct 341 ms 678972 KB Output is correct
46 Correct 325 ms 675924 KB Output is correct
47 Correct 414 ms 714064 KB Output is correct
48 Correct 432 ms 714188 KB Output is correct
49 Correct 250 ms 636288 KB Output is correct
50 Correct 224 ms 636060 KB Output is correct
51 Correct 241 ms 635728 KB Output is correct
52 Correct 238 ms 635340 KB Output is correct
53 Correct 230 ms 636240 KB Output is correct
54 Correct 234 ms 636044 KB Output is correct
55 Correct 238 ms 636240 KB Output is correct
56 Correct 236 ms 636264 KB Output is correct
57 Correct 243 ms 636240 KB Output is correct
58 Correct 237 ms 635576 KB Output is correct
59 Correct 238 ms 635732 KB Output is correct
60 Correct 239 ms 635280 KB Output is correct
61 Correct 1059 ms 932020 KB Output is correct
62 Runtime error 785 ms 1048576 KB Execution killed with signal 9
63 Halted 0 ms 0 KB -