oj.uz

Submission #154564

# Submission time Handle Problem Language Result Execution time Memory
154564 2019-09-22T17:53:57 Z liwi Rectangles (IOI19_rect) C++14
49 / 100
 545 ms 451716 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4,popcnt,abm,mmx,tune=native")

#include <bits/stdc++.h>

//using namespace std;

#define INT_INF 0x3f3f3f3f
#define mp std::make_pair

#define MAXN 2001

typedef long long ll;
typedef std::pair<int,int> pii;

int num_rows,num_cols,arr[MAXN][MAXN],bit[MAXN],cnt[MAXN][MAXN],ans,l,r,lst[MAXN],pp;
std::vector<pii> row_dp[MAXN][MAXN],col_dp[MAXN][MAXN];
std::vector<std::pair<pii,int>> dep[MAXN];
pii dq[MAXN];

inline void update(int i, int val, int curr){
	for(; i<=num_cols; i+=i&-i){
		if(lst[i] != curr) bit[i] = val, lst[i] = curr;
		else bit[i]+=val;
	}
}

inline int query(int i, int curr){
	int res = 0;
	for(; i>0; i-=i&-i)
		if(lst[i] == curr)
			res+=bit[i];
	return res;
}

inline void init_rows(){
//	memset(cnt,0,sizeof cnt);
	for(int i=2; i<num_rows; i++){
		l = 1, r = 0;
		for(int k=1; k<=num_cols; k++){
			while(r-l+1 > 0 && dq[r].first < arr[i][k]) r--;
			int lft = (r-l+1>0?dq[r].second:INT_INF);
			if(lft < k-1 && (row_dp[lft+1][k-1].empty() || row_dp[lft+1][k-1].back().first != i))
				row_dp[lft+1][k-1].emplace_back(i,i), cnt[lft+1][k-1]++; //rows[i].pb(mp(lft+1,k-1));
			while(r-l+1 > 0 && dq[r].first == arr[i][k]) r--;
			dq[++r] = mp(arr[i][k],k);
		}
		l = 1, r = 0;
		for(int k=num_cols; k>=1; k--){
			while(r-l+1 > 0 && dq[r].first < arr[i][k]) r--;
			int rgt = (r-l+1>0?dq[r].second:-INT_INF);
			if(rgt > k+1 && (row_dp[k+1][rgt-1].empty() || row_dp[k+1][rgt-1].back().first != i))
				row_dp[k+1][rgt-1].emplace_back(i,i), cnt[k+1][rgt-1]++; //rows[i].pb(mp(k+1,rgt-1));
			while(r-l+1 > 0 && dq[r].first == arr[i][k]) r--;
			dq[++r] = mp(arr[i][k],k);
		}
	}
}

inline void init_cols(){
	memset(cnt,0,sizeof cnt);
	for(int i=2; i<num_cols; i++){
		l = 1, r = 0;
		for(int k=1; k<=num_rows; k++){
			while(r-l+1 > 0 && dq[r].first < arr[k][i]) r--;
			int lft = (r-l+1>0?dq[r].second:INT_INF);
			if(lft < k-1 && (col_dp[lft+1][k-1].empty() || col_dp[lft+1][k-1].back().first != i))
				col_dp[lft+1][k-1].emplace_back(i,i), cnt[lft+1][k-1]++; //cols[i].pb(mp(lft+1,k-1));
			while(r-l+1 > 0 && dq[r].first == arr[k][i]) r--;
			dq[++r] = mp(arr[k][i],k);
		}
		l = 1, r = 0;
		for(int k=num_rows; k>=1; k--){
			while(r-l+1 > 0 && dq[r].first < arr[k][i]) r--;
			int rgt = (r-l+1>0?dq[r].second:-INT_INF);
			if(rgt > k+1 && (col_dp[k+1][rgt-1].empty() || col_dp[k+1][rgt-1].back().first != i))
				col_dp[k+1][rgt-1].emplace_back(i,i), cnt[k+1][rgt-1]++; //cols[i].pb(mp(k+1,rgt-1));
			while(r-l+1 > 0 && dq[r].first == arr[k][i]) r--;
			dq[++r] = mp(arr[k][i],k);
		}
	}
}

inline void calc_hor_dp(){
//	for(int i=2; i<num_rows; i++){
//		sort(all(rows[i])); complete_unique(rows[i]);
//		for(pii check:rows[i]){
//			h_segs[check.first][check.second].pb(i);
////			r_range[i][check.first].pb(check.second);
//		}
//		rows[i].clear();
//	}
	for(int l=2; l<=num_cols-1; l++){
		for(int r=l; r<=num_cols-1; r++){
			if(cnt[l][r] == 0) continue;
			#define nums row_dp[l][r]
//			std::vector<pii> &nums = row_dp[l][r];
//			sort(all(nums)); complete_unique(nums);
//			std::vector<pii> t;
			int lst = 0;
			for(int i=1; i<cnt[l][r]; i++){
				if(nums[i].first == nums[i-1].first+1) continue;
				for(int k=nums[lst].first; k<=nums[i-1].first; k++)
					dep[nums[i-1].first-k+1].emplace_back(mp(k,l),r);
//					row_dp[k][l].pb(mp(nums[i-1].first-k+1,r));
				lst = i;
			}
			for(int k=nums[lst].first; k<=nums[cnt[l][r]-1].first; k++)
				dep[nums[cnt[l][r]-1].first-k+1].emplace_back(mp(k,l),r);
//				row_dp[k][l].pb(mp(nums[cnt[l][r]-1].first-k+1,r));
			nums.clear();
		}
	}
	for(int i=1; i<=num_rows; i++){
		for(auto &check:dep[i])
			row_dp[check.first.first][check.first.second].emplace_back(i,check.second);
	}
//	for(int l=2; l<=num_cols-1; l++){
//		for(int r=l; r<=num_cols-1; r++){
//			reverse(all(row_dp[l][r]));
//			while(cnt[l][r]--) row_dp[l][r].pop_back();
//			reverse(all(row_dp[l][r]));
//		}
//	}
}

inline void calc_col_dp(){
//	for(int i=2; i<num_cols; i++){
//		sort(all(cols[i])); complete_unique(cols[i]);
//		for(pii check:cols[i]){
//			v_segs[check.first][check.second].pb(i);
////			v_range[check.first][i].pb(check.second);
//		}
//		cols[i].clear();
//	}
	for(int l=2; l<=num_rows-1; l++){
		for(int r=l; r<=num_rows-1; r++){
			if(cnt[l][r] == 0) continue;
			#define nums col_dp[l][r]
//			std::vector<pii> &nums = col_dp[l][r];
//			sort(all(nums)); complete_unique(nums);
			int lst = 0;
			for(int i=1; i<cnt[l][r]; i++){
				if(nums[i].first == nums[i-1].first+1) continue;
				for(int k=nums[lst].first; k<=nums[i-1].first; k++)
					col_dp[l][k].emplace_back(r,nums[i-1].first);
				lst = i;
			}
			for(int k=nums[lst].first; k<=nums[cnt[l][r]-1].first; k++)
				col_dp[l][k].emplace_back(r,nums[cnt[l][r]-1].first);
		}
	}
//	for(int l=2; l<=num_cols-1; l++){
//		for(int r=l; r<=num_cols-1; r++){
//			reverse(all(col_dp[l][r]));
//			while(cnt[l][r]--) col_dp[l][r].pop_back();
//			reverse(all(col_dp[l][r]));
//		}
//	}
}

ll count_rectangles(std::vector<std::vector<int>> a){
	ans = 0, num_rows = (int)a.size(), num_cols = (int)a[0].size();
	for(int i=0; i<a.size(); i++)
		for(int k=0; k<a[i].size(); k++)
			arr[i+1][k+1] = a[i][k];
	init_rows(); calc_hor_dp();
	init_cols(); calc_col_dp();
	for(int i=num_rows-1; i>=2; i--){
		for(int k=num_cols-1; k>=2; k--){
//			sort(all(row_dp[i][k]));
//			sort(all(col_dp[i][k]));
			int ptr = cnt[i][k], res = 0, cc = 0; ++pp;
			for(int v=0; v<row_dp[i][k].size(); v++){
//				pii curr = row_dp[i][k][v];
				while(ptr < col_dp[i][k].size() && col_dp[i][k][ptr].first-i+1 <= row_dp[i][k][v].first){
//					assert(col_dp[i][k][ptr].second>=k);
					update(col_dp[i][k][ptr].second-k+1,1,pp);
					ptr++, cc++;
				}
				res+=cc-query(row_dp[i][k][v].second-k,pp);
			}
//			while(--ptr >= cnt[i][k]) update(col_dp[i][k][ptr].second-k+1,-1);
			ans+=res;
		}
	}
	return ans;
}

Compilation message

rect.cpp:140:0: warning: "nums" redefined
    #define nums col_dp[l][r]
 
rect.cpp:97:0: note: this is the location of the previous definition
    #define nums row_dp[l][r]
 
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:165:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<a.size(); i++)
               ~^~~~~~~~~
rect.cpp:166:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0; k<a[i].size(); k++)
                ~^~~~~~~~~~~~
rect.cpp:175:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int v=0; v<row_dp[i][k].size(); v++){
                 ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:177:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr < col_dp[i][k].size() && col_dp[i][k][ptr].first-i+1 <= row_dp[i][k][v].first){
           ~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 204208 KB Output is correct
2 Correct 201 ms 204252 KB Output is correct
3 Correct 200 ms 204280 KB Output is correct
4 Correct 203 ms 204316 KB Output is correct
5 Correct 201 ms 204152 KB Output is correct
6 Correct 202 ms 204280 KB Output is correct
7 Correct 201 ms 204280 KB Output is correct
8 Correct 199 ms 204280 KB Output is correct
9 Correct 203 ms 204284 KB Output is correct
10 Correct 201 ms 204268 KB Output is correct
11 Correct 201 ms 204472 KB Output is correct
12 Correct 202 ms 204380 KB Output is correct
13 Correct 240 ms 204152 KB Output is correct
14 Correct 201 ms 204152 KB Output is correct
15 Correct 200 ms 204176 KB Output is correct
16 Correct 201 ms 204108 KB Output is correct
17 Correct 200 ms 204188 KB Output is correct
18 Correct 202 ms 204132 KB Output is correct
19 Correct 201 ms 204356 KB Output is correct
20 Correct 201 ms 204252 KB Output is correct
21 Correct 200 ms 204244 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 204208 KB Output is correct
2 Correct 201 ms 204252 KB Output is correct
3 Correct 200 ms 204280 KB Output is correct
4 Correct 203 ms 204316 KB Output is correct
5 Correct 201 ms 204152 KB Output is correct
6 Correct 202 ms 204280 KB Output is correct
7 Correct 201 ms 204280 KB Output is correct
8 Correct 199 ms 204280 KB Output is correct
9 Correct 203 ms 204284 KB Output is correct
10 Correct 201 ms 204268 KB Output is correct
11 Correct 201 ms 204472 KB Output is correct
12 Correct 202 ms 204380 KB Output is correct
13 Correct 240 ms 204152 KB Output is correct
14 Correct 201 ms 204152 KB Output is correct
15 Correct 200 ms 204176 KB Output is correct
16 Correct 201 ms 204108 KB Output is correct
17 Correct 201 ms 205304 KB Output is correct
18 Correct 201 ms 205176 KB Output is correct
19 Correct 203 ms 205176 KB Output is correct
20 Correct 202 ms 204792 KB Output is correct
21 Correct 203 ms 204892 KB Output is correct
22 Correct 205 ms 204948 KB Output is correct
23 Correct 203 ms 204892 KB Output is correct
24 Correct 201 ms 204664 KB Output is correct
25 Correct 200 ms 204188 KB Output is correct
26 Correct 202 ms 204132 KB Output is correct
27 Correct 201 ms 204356 KB Output is correct
28 Correct 201 ms 204252 KB Output is correct
29 Correct 200 ms 204244 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 204208 KB Output is correct
2 Correct 201 ms 204252 KB Output is correct
3 Correct 200 ms 204280 KB Output is correct
4 Correct 203 ms 204316 KB Output is correct
5 Correct 201 ms 204152 KB Output is correct
6 Correct 202 ms 204280 KB Output is correct
7 Correct 201 ms 204280 KB Output is correct
8 Correct 199 ms 204280 KB Output is correct
9 Correct 203 ms 204284 KB Output is correct
10 Correct 201 ms 204268 KB Output is correct
11 Correct 201 ms 204472 KB Output is correct
12 Correct 202 ms 204380 KB Output is correct
13 Correct 240 ms 204152 KB Output is correct
14 Correct 201 ms 204152 KB Output is correct
15 Correct 200 ms 204176 KB Output is correct
16 Correct 201 ms 204108 KB Output is correct
17 Correct 201 ms 205304 KB Output is correct
18 Correct 201 ms 205176 KB Output is correct
19 Correct 203 ms 205176 KB Output is correct
20 Correct 202 ms 204792 KB Output is correct
21 Correct 203 ms 204892 KB Output is correct
22 Correct 205 ms 204948 KB Output is correct
23 Correct 203 ms 204892 KB Output is correct
24 Correct 201 ms 204664 KB Output is correct
25 Correct 215 ms 209436 KB Output is correct
26 Correct 223 ms 209684 KB Output is correct
27 Correct 215 ms 209656 KB Output is correct
28 Correct 211 ms 206848 KB Output is correct
29 Correct 233 ms 208392 KB Output is correct
30 Correct 222 ms 208568 KB Output is correct
31 Correct 221 ms 208276 KB Output is correct
32 Correct 220 ms 208192 KB Output is correct
33 Correct 200 ms 204188 KB Output is correct
34 Correct 202 ms 204132 KB Output is correct
35 Correct 201 ms 204356 KB Output is correct
36 Correct 201 ms 204252 KB Output is correct
37 Correct 200 ms 204244 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 204208 KB Output is correct
2 Correct 201 ms 204252 KB Output is correct
3 Correct 200 ms 204280 KB Output is correct
4 Correct 203 ms 204316 KB Output is correct
5 Correct 201 ms 204152 KB Output is correct
6 Correct 202 ms 204280 KB Output is correct
7 Correct 201 ms 204280 KB Output is correct
8 Correct 199 ms 204280 KB Output is correct
9 Correct 203 ms 204284 KB Output is correct
10 Correct 201 ms 204268 KB Output is correct
11 Correct 201 ms 204472 KB Output is correct
12 Correct 202 ms 204380 KB Output is correct
13 Correct 240 ms 204152 KB Output is correct
14 Correct 201 ms 204152 KB Output is correct
15 Correct 200 ms 204176 KB Output is correct
16 Correct 201 ms 204108 KB Output is correct
17 Correct 201 ms 205304 KB Output is correct
18 Correct 201 ms 205176 KB Output is correct
19 Correct 203 ms 205176 KB Output is correct
20 Correct 202 ms 204792 KB Output is correct
21 Correct 203 ms 204892 KB Output is correct
22 Correct 205 ms 204948 KB Output is correct
23 Correct 203 ms 204892 KB Output is correct
24 Correct 201 ms 204664 KB Output is correct
25 Correct 215 ms 209436 KB Output is correct
26 Correct 223 ms 209684 KB Output is correct
27 Correct 215 ms 209656 KB Output is correct
28 Correct 211 ms 206848 KB Output is correct
29 Correct 233 ms 208392 KB Output is correct
30 Correct 222 ms 208568 KB Output is correct
31 Correct 221 ms 208276 KB Output is correct
32 Correct 220 ms 208192 KB Output is correct
33 Correct 385 ms 239436 KB Output is correct
34 Correct 355 ms 238408 KB Output is correct
35 Correct 341 ms 238704 KB Output is correct
36 Correct 297 ms 237832 KB Output is correct
37 Correct 407 ms 263952 KB Output is correct
38 Correct 412 ms 263876 KB Output is correct
39 Correct 406 ms 263916 KB Output is correct
40 Correct 406 ms 260304 KB Output is correct
41 Correct 320 ms 225300 KB Output is correct
42 Correct 373 ms 230304 KB Output is correct
43 Correct 542 ms 246820 KB Output is correct
44 Correct 545 ms 247716 KB Output is correct
45 Correct 365 ms 227576 KB Output is correct
46 Correct 361 ms 226060 KB Output is correct
47 Correct 503 ms 245248 KB Output is correct
48 Correct 506 ms 245492 KB Output is correct
49 Correct 200 ms 204188 KB Output is correct
50 Correct 202 ms 204132 KB Output is correct
51 Correct 201 ms 204356 KB Output is correct
52 Correct 201 ms 204252 KB Output is correct
53 Correct 200 ms 204244 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 448 ms 397720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 204220 KB Output is correct
2 Runtime error 513 ms 451716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 204208 KB Output is correct
2 Correct 201 ms 204252 KB Output is correct
3 Correct 200 ms 204280 KB Output is correct
4 Correct 203 ms 204316 KB Output is correct
5 Correct 201 ms 204152 KB Output is correct
6 Correct 202 ms 204280 KB Output is correct
7 Correct 201 ms 204280 KB Output is correct
8 Correct 199 ms 204280 KB Output is correct
9 Correct 203 ms 204284 KB Output is correct
10 Correct 201 ms 204268 KB Output is correct
11 Correct 201 ms 204472 KB Output is correct
12 Correct 202 ms 204380 KB Output is correct
13 Correct 240 ms 204152 KB Output is correct
14 Correct 201 ms 204152 KB Output is correct
15 Correct 200 ms 204176 KB Output is correct
16 Correct 201 ms 204108 KB Output is correct
17 Correct 201 ms 205304 KB Output is correct
18 Correct 201 ms 205176 KB Output is correct
19 Correct 203 ms 205176 KB Output is correct
20 Correct 202 ms 204792 KB Output is correct
21 Correct 203 ms 204892 KB Output is correct
22 Correct 205 ms 204948 KB Output is correct
23 Correct 203 ms 204892 KB Output is correct
24 Correct 201 ms 204664 KB Output is correct
25 Correct 215 ms 209436 KB Output is correct
26 Correct 223 ms 209684 KB Output is correct
27 Correct 215 ms 209656 KB Output is correct
28 Correct 211 ms 206848 KB Output is correct
29 Correct 233 ms 208392 KB Output is correct
30 Correct 222 ms 208568 KB Output is correct
31 Correct 221 ms 208276 KB Output is correct
32 Correct 220 ms 208192 KB Output is correct
33 Correct 385 ms 239436 KB Output is correct
34 Correct 355 ms 238408 KB Output is correct
35 Correct 341 ms 238704 KB Output is correct
36 Correct 297 ms 237832 KB Output is correct
37 Correct 407 ms 263952 KB Output is correct
38 Correct 412 ms 263876 KB Output is correct
39 Correct 406 ms 263916 KB Output is correct
40 Correct 406 ms 260304 KB Output is correct
41 Correct 320 ms 225300 KB Output is correct
42 Correct 373 ms 230304 KB Output is correct
43 Correct 542 ms 246820 KB Output is correct
44 Correct 545 ms 247716 KB Output is correct
45 Correct 365 ms 227576 KB Output is correct
46 Correct 361 ms 226060 KB Output is correct
47 Correct 503 ms 245248 KB Output is correct
48 Correct 506 ms 245492 KB Output is correct
49 Runtime error 448 ms 397720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Halted 0 ms 0 KB -