oj.uz

Submission #154443

# Submission time Handle Problem Language Result Execution time Memory
154443 2019-09-21T21:01:26 Z Dormi Rectangles (IOI19_rect) C++14
100 / 100
 4469 ms 736244 KB 
#pragma GCC optimize "Ofast"
#pragma GCC optimize "unroll-loops"
#pragma GCC target "sse,sse2,sse3,sse4,abm,avx,mmx,popcnt,tune=native"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=2500;
int bit[MAXN+1];
int n,m;
vector<pii> rowranges[MAXN][MAXN];
vector<pii> colranges[MAXN][MAXN];
int preloc[MAXN];
int sufloc[MAXN];
pii deq[MAXN];
void update(int loc, int val){
	for(;loc<=n;loc+=loc&-loc)bit[loc]+=val;
}
int sum(int loc){
	int ans=0;
	for(;loc>0;loc-=loc&-loc)ans+=bit[loc];
	return ans;
}
long long count_rectangles(std::vector<std::vector<int>> a){
	n=a.size();
	m=a[0].size();
	for(int i=0;i<n;i++){
		int l=0,r=-1;
		for(int j=m-1;j>=0;j--){
			while(r>=l&&deq[r].second<=a[i][j])r--;
			if(r>=l)sufloc[j]=deq[r].first;
			else sufloc[j]=-1;
			deq[++r]={j,a[i][j]};
		}
		l=0,r=-1;
		for(int j=0;j<m;j++){
			while(r>=l&&deq[r].second<=a[i][j])r--;
			if(r>=l)preloc[j]=deq[r].first;
			else preloc[j]=-1;
			deq[++r]={j,a[i][j]};
			if(preloc[j]!=-1&&sufloc[j]!=-1){
				while(rowranges[i][preloc[j]+1].size()&&rowranges[i][preloc[j]+1].back().first==sufloc[j]-1)rowranges[i][preloc[j]+1].pop_back();
				rowranges[i][preloc[j]+1].emplace_back(sufloc[j]-1,1);
			}
		}
	}
	for(int i=0;i<m;i++){
		int l=0,r=-1;
		for(int j=n-1;j>=0;j--){
			while(r>=l&&deq[r].second<=a[j][i])r--;
			if(r>=l)sufloc[j]=deq[r].first;
			else sufloc[j]=-1;
			deq[++r]={j,a[j][i]};
		}
		l=0,r=-1;
		for(int j=0;j<n;j++){
			while(r>=l&&deq[r].second<=a[j][i])r--;
			if(r>=l)preloc[j]=deq[r].first;
			else preloc[j]=-1;
			deq[++r]={j,a[j][i]};
			if(preloc[j]!=-1&&sufloc[j]!=-1){
				while(colranges[preloc[j]+1][i].size()&&colranges[preloc[j]+1][i].back().first==sufloc[j]-1)colranges[preloc[j]+1][i].pop_back();
				colranges[preloc[j]+1][i].emplace_back(sufloc[j]-1,1);
			}
		}
	}
	for(int i=0;i<m;i++){
		for(int j=n-2;j>=0;j--){
			int l=0,r=0;
			while(l<rowranges[j][i].size()&&r<rowranges[j+1][i].size()){
				if(rowranges[j][i][l].first==rowranges[j+1][i][r].first){
					rowranges[j][i][l].second+=rowranges[j+1][i][r].second;
					l++;
				}
				else if(rowranges[j][i][l].first>rowranges[j+1][i][r].first){
					r++;
				}
				else l++;
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=m-2;j>=0;j--){
			int l=0,r=0;
			while(l<colranges[i][j].size()&&r<colranges[i][j+1].size()){
				if(colranges[i][j][l].first==colranges[i][j+1][r].first){
					colranges[i][j][l].second+=colranges[i][j+1][r].second;
					l++;
				}
				else if(colranges[i][j][l].first>colranges[i][j+1][r].first){
					r++;
				}
				else l++;
			}
		}
	}
	int cnt=0;
	auto f = [&] (const pii& a, const pii& b) {
		return a.second<b.second;
	};
	for(int i=0;i<n;i++)for(int j=0;j<m;j++){
			sort(colranges[i][j].begin(),colranges[i][j].end(),f);
			int r=colranges[i][j].size();
			for(int k=(int)rowranges[i][j].size()-1;k>=0;k--){
				while(r>0&&colranges[i][j][r-1].second+j-1>=rowranges[i][j][k].first){
					r-=1;
					update(colranges[i][j][r].first+1,1);
				}
				cnt+=sum(rowranges[i][j][k].second+i);
			}
			for(int k=r;k<colranges[i][j].size();k++)update(colranges[i][j][k].first+1,-1);
		}
	return cnt;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:69:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(l<rowranges[j][i].size()&&r<rowranges[j+1][i].size()){
          ~^~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:69:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(l<rowranges[j][i].size()&&r<rowranges[j+1][i].size()){
                                    ~^~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:84:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(l<colranges[i][j].size()&&r<colranges[i][j+1].size()){
          ~^~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:84:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(l<colranges[i][j].size()&&r<colranges[i][j+1].size()){
                                    ~^~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:110:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=r;k<colranges[i][j].size();k++)update(colranges[i][j][k].first+1,-1);
                ~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 293892 KB Output is correct
2 Correct 289 ms 293964 KB Output is correct
3 Correct 284 ms 293924 KB Output is correct
4 Correct 320 ms 294008 KB Output is correct
5 Correct 298 ms 293880 KB Output is correct
6 Correct 287 ms 294008 KB Output is correct
7 Correct 286 ms 293904 KB Output is correct
8 Correct 285 ms 293860 KB Output is correct
9 Correct 287 ms 293928 KB Output is correct
10 Correct 285 ms 293924 KB Output is correct
11 Correct 286 ms 294008 KB Output is correct
12 Correct 287 ms 293880 KB Output is correct
13 Correct 286 ms 293896 KB Output is correct
14 Correct 288 ms 293792 KB Output is correct
15 Correct 287 ms 293884 KB Output is correct
16 Correct 286 ms 293980 KB Output is correct
17 Correct 292 ms 293864 KB Output is correct
18 Correct 289 ms 293964 KB Output is correct
19 Correct 323 ms 293880 KB Output is correct
20 Correct 299 ms 294008 KB Output is correct
21 Correct 288 ms 293936 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 293892 KB Output is correct
2 Correct 289 ms 293964 KB Output is correct
3 Correct 284 ms 293924 KB Output is correct
4 Correct 320 ms 294008 KB Output is correct
5 Correct 298 ms 293880 KB Output is correct
6 Correct 287 ms 294008 KB Output is correct
7 Correct 286 ms 293904 KB Output is correct
8 Correct 285 ms 293860 KB Output is correct
9 Correct 287 ms 293928 KB Output is correct
10 Correct 285 ms 293924 KB Output is correct
11 Correct 286 ms 294008 KB Output is correct
12 Correct 287 ms 293880 KB Output is correct
13 Correct 286 ms 293896 KB Output is correct
14 Correct 288 ms 293792 KB Output is correct
15 Correct 287 ms 293884 KB Output is correct
16 Correct 286 ms 293980 KB Output is correct
17 Correct 286 ms 294364 KB Output is correct
18 Correct 303 ms 294420 KB Output is correct
19 Correct 328 ms 294372 KB Output is correct
20 Correct 294 ms 294056 KB Output is correct
21 Correct 294 ms 294136 KB Output is correct
22 Correct 302 ms 294264 KB Output is correct
23 Correct 292 ms 294084 KB Output is correct
24 Correct 289 ms 294008 KB Output is correct
25 Correct 292 ms 293864 KB Output is correct
26 Correct 289 ms 293964 KB Output is correct
27 Correct 323 ms 293880 KB Output is correct
28 Correct 299 ms 294008 KB Output is correct
29 Correct 288 ms 293936 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 293892 KB Output is correct
2 Correct 289 ms 293964 KB Output is correct
3 Correct 284 ms 293924 KB Output is correct
4 Correct 320 ms 294008 KB Output is correct
5 Correct 298 ms 293880 KB Output is correct
6 Correct 287 ms 294008 KB Output is correct
7 Correct 286 ms 293904 KB Output is correct
8 Correct 285 ms 293860 KB Output is correct
9 Correct 287 ms 293928 KB Output is correct
10 Correct 285 ms 293924 KB Output is correct
11 Correct 286 ms 294008 KB Output is correct
12 Correct 287 ms 293880 KB Output is correct
13 Correct 286 ms 293896 KB Output is correct
14 Correct 288 ms 293792 KB Output is correct
15 Correct 287 ms 293884 KB Output is correct
16 Correct 286 ms 293980 KB Output is correct
17 Correct 286 ms 294364 KB Output is correct
18 Correct 303 ms 294420 KB Output is correct
19 Correct 328 ms 294372 KB Output is correct
20 Correct 294 ms 294056 KB Output is correct
21 Correct 294 ms 294136 KB Output is correct
22 Correct 302 ms 294264 KB Output is correct
23 Correct 292 ms 294084 KB Output is correct
24 Correct 289 ms 294008 KB Output is correct
25 Correct 297 ms 296940 KB Output is correct
26 Correct 346 ms 296848 KB Output is correct
27 Correct 315 ms 296952 KB Output is correct
28 Correct 294 ms 295048 KB Output is correct
29 Correct 301 ms 295900 KB Output is correct
30 Correct 301 ms 295880 KB Output is correct
31 Correct 324 ms 295832 KB Output is correct
32 Correct 302 ms 295892 KB Output is correct
33 Correct 292 ms 293864 KB Output is correct
34 Correct 289 ms 293964 KB Output is correct
35 Correct 323 ms 293880 KB Output is correct
36 Correct 299 ms 294008 KB Output is correct
37 Correct 288 ms 293936 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 293892 KB Output is correct
2 Correct 289 ms 293964 KB Output is correct
3 Correct 284 ms 293924 KB Output is correct
4 Correct 320 ms 294008 KB Output is correct
5 Correct 298 ms 293880 KB Output is correct
6 Correct 287 ms 294008 KB Output is correct
7 Correct 286 ms 293904 KB Output is correct
8 Correct 285 ms 293860 KB Output is correct
9 Correct 287 ms 293928 KB Output is correct
10 Correct 285 ms 293924 KB Output is correct
11 Correct 286 ms 294008 KB Output is correct
12 Correct 287 ms 293880 KB Output is correct
13 Correct 286 ms 293896 KB Output is correct
14 Correct 288 ms 293792 KB Output is correct
15 Correct 287 ms 293884 KB Output is correct
16 Correct 286 ms 293980 KB Output is correct
17 Correct 286 ms 294364 KB Output is correct
18 Correct 303 ms 294420 KB Output is correct
19 Correct 328 ms 294372 KB Output is correct
20 Correct 294 ms 294056 KB Output is correct
21 Correct 294 ms 294136 KB Output is correct
22 Correct 302 ms 294264 KB Output is correct
23 Correct 292 ms 294084 KB Output is correct
24 Correct 289 ms 294008 KB Output is correct
25 Correct 297 ms 296940 KB Output is correct
26 Correct 346 ms 296848 KB Output is correct
27 Correct 315 ms 296952 KB Output is correct
28 Correct 294 ms 295048 KB Output is correct
29 Correct 301 ms 295900 KB Output is correct
30 Correct 301 ms 295880 KB Output is correct
31 Correct 324 ms 295832 KB Output is correct
32 Correct 302 ms 295892 KB Output is correct
33 Correct 395 ms 316016 KB Output is correct
34 Correct 372 ms 311416 KB Output is correct
35 Correct 366 ms 311212 KB Output is correct
36 Correct 351 ms 306552 KB Output is correct
37 Correct 469 ms 331388 KB Output is correct
38 Correct 469 ms 331536 KB Output is correct
39 Correct 471 ms 331384 KB Output is correct
40 Correct 451 ms 329076 KB Output is correct
41 Correct 382 ms 306296 KB Output is correct
42 Correct 424 ms 308984 KB Output is correct
43 Correct 580 ms 317436 KB Output is correct
44 Correct 499 ms 318988 KB Output is correct
45 Correct 421 ms 306728 KB Output is correct
46 Correct 386 ms 306756 KB Output is correct
47 Correct 473 ms 317204 KB Output is correct
48 Correct 493 ms 317540 KB Output is correct
49 Correct 292 ms 293864 KB Output is correct
50 Correct 289 ms 293964 KB Output is correct
51 Correct 323 ms 293880 KB Output is correct
52 Correct 299 ms 294008 KB Output is correct
53 Correct 288 ms 293936 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 294360 KB Output is correct
2 Correct 285 ms 294264 KB Output is correct
3 Correct 286 ms 293880 KB Output is correct
4 Correct 287 ms 293880 KB Output is correct
5 Correct 287 ms 294208 KB Output is correct
6 Correct 297 ms 294352 KB Output is correct
7 Correct 309 ms 294204 KB Output is correct
8 Correct 287 ms 294264 KB Output is correct
9 Correct 305 ms 294136 KB Output is correct
10 Correct 310 ms 294084 KB Output is correct
11 Correct 288 ms 294168 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 293828 KB Output is correct
2 Correct 881 ms 364608 KB Output is correct
3 Correct 1701 ms 442936 KB Output is correct
4 Correct 1718 ms 443880 KB Output is correct
5 Correct 1824 ms 443916 KB Output is correct
6 Correct 448 ms 321556 KB Output is correct
7 Correct 669 ms 343012 KB Output is correct
8 Correct 684 ms 346104 KB Output is correct
9 Correct 292 ms 293864 KB Output is correct
10 Correct 289 ms 293964 KB Output is correct
11 Correct 323 ms 293880 KB Output is correct
12 Correct 299 ms 294008 KB Output is correct
13 Correct 288 ms 293936 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 293892 KB Output is correct
2 Correct 289 ms 293964 KB Output is correct
3 Correct 284 ms 293924 KB Output is correct
4 Correct 320 ms 294008 KB Output is correct
5 Correct 298 ms 293880 KB Output is correct
6 Correct 287 ms 294008 KB Output is correct
7 Correct 286 ms 293904 KB Output is correct
8 Correct 285 ms 293860 KB Output is correct
9 Correct 287 ms 293928 KB Output is correct
10 Correct 285 ms 293924 KB Output is correct
11 Correct 286 ms 294008 KB Output is correct
12 Correct 287 ms 293880 KB Output is correct
13 Correct 286 ms 293896 KB Output is correct
14 Correct 288 ms 293792 KB Output is correct
15 Correct 287 ms 293884 KB Output is correct
16 Correct 286 ms 293980 KB Output is correct
17 Correct 286 ms 294364 KB Output is correct
18 Correct 303 ms 294420 KB Output is correct
19 Correct 328 ms 294372 KB Output is correct
20 Correct 294 ms 294056 KB Output is correct
21 Correct 294 ms 294136 KB Output is correct
22 Correct 302 ms 294264 KB Output is correct
23 Correct 292 ms 294084 KB Output is correct
24 Correct 289 ms 294008 KB Output is correct
25 Correct 297 ms 296940 KB Output is correct
26 Correct 346 ms 296848 KB Output is correct
27 Correct 315 ms 296952 KB Output is correct
28 Correct 294 ms 295048 KB Output is correct
29 Correct 301 ms 295900 KB Output is correct
30 Correct 301 ms 295880 KB Output is correct
31 Correct 324 ms 295832 KB Output is correct
32 Correct 302 ms 295892 KB Output is correct
33 Correct 395 ms 316016 KB Output is correct
34 Correct 372 ms 311416 KB Output is correct
35 Correct 366 ms 311212 KB Output is correct
36 Correct 351 ms 306552 KB Output is correct
37 Correct 469 ms 331388 KB Output is correct
38 Correct 469 ms 331536 KB Output is correct
39 Correct 471 ms 331384 KB Output is correct
40 Correct 451 ms 329076 KB Output is correct
41 Correct 382 ms 306296 KB Output is correct
42 Correct 424 ms 308984 KB Output is correct
43 Correct 580 ms 317436 KB Output is correct
44 Correct 499 ms 318988 KB Output is correct
45 Correct 421 ms 306728 KB Output is correct
46 Correct 386 ms 306756 KB Output is correct
47 Correct 473 ms 317204 KB Output is correct
48 Correct 493 ms 317540 KB Output is correct
49 Correct 286 ms 294360 KB Output is correct
50 Correct 285 ms 294264 KB Output is correct
51 Correct 286 ms 293880 KB Output is correct
52 Correct 287 ms 293880 KB Output is correct
53 Correct 287 ms 294208 KB Output is correct
54 Correct 297 ms 294352 KB Output is correct
55 Correct 309 ms 294204 KB Output is correct
56 Correct 287 ms 294264 KB Output is correct
57 Correct 305 ms 294136 KB Output is correct
58 Correct 310 ms 294084 KB Output is correct
59 Correct 288 ms 294168 KB Output is correct
60 Correct 290 ms 293828 KB Output is correct
61 Correct 881 ms 364608 KB Output is correct
62 Correct 1701 ms 442936 KB Output is correct
63 Correct 1718 ms 443880 KB Output is correct
64 Correct 1824 ms 443916 KB Output is correct
65 Correct 448 ms 321556 KB Output is correct
66 Correct 669 ms 343012 KB Output is correct
67 Correct 684 ms 346104 KB Output is correct
68 Correct 1913 ms 538916 KB Output is correct
69 Correct 2023 ms 471916 KB Output is correct
70 Correct 1534 ms 471880 KB Output is correct
71 Correct 1242 ms 404728 KB Output is correct
72 Correct 4469 ms 734216 KB Output is correct
73 Correct 1989 ms 464724 KB Output is correct
74 Correct 2153 ms 472044 KB Output is correct
75 Correct 3290 ms 574148 KB Output is correct
76 Correct 2215 ms 463400 KB Output is correct
77 Correct 2873 ms 519764 KB Output is correct
78 Correct 3402 ms 576208 KB Output is correct
79 Correct 1960 ms 452364 KB Output is correct
80 Correct 3263 ms 562164 KB Output is correct
81 Correct 3177 ms 551924 KB Output is correct
82 Correct 2478 ms 558028 KB Output is correct
83 Correct 4326 ms 733856 KB Output is correct
84 Correct 4288 ms 734296 KB Output is correct
85 Correct 4400 ms 736244 KB Output is correct
86 Correct 292 ms 293864 KB Output is correct
87 Correct 289 ms 293964 KB Output is correct
88 Correct 323 ms 293880 KB Output is correct
89 Correct 299 ms 294008 KB Output is correct
90 Correct 288 ms 293936 KB Output is correct