oj.uz

Submission #154455

# Submission time Handle Problem Language Result Execution time Memory
154455 2019-09-22T00:56:23 Z liwi Rectangles (IOI19_rect) C++14
72 / 100
 2793 ms 1048576 KB 
#include "rect.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define MOD2 1494318097
#define SEED 131
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);

#define MAXN 2505

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

mt19937 g1(time(0));

int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}

ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

int num_rows,num_cols,arr[MAXN][MAXN],bit[MAXN],ans;
vector<pii> row_dp[MAXN][MAXN],col_dp[MAXN][MAXN];
//vector<pii> rows[MAXN],cols[MAXN];
vector<int> h_segs[MAXN][MAXN],v_segs[MAXN][MAXN];
//vector<int> r_range[MAXN][MAXN],v_range[MAXN][MAXN];

inline void update(int pos, int val){
	for(int i=pos; i<=num_cols; i+=i&-i)
		bit[i]+=val;
}

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

inline void init_rows(){
	for(int i=2; i<num_rows; i++){
		deque<pii> dq;
		for(int k=1; k<=num_cols; k++){
			while(dq.size() && dq.back().first < arr[i][k]) dq.pop_back();
			int lft = (dq.size()?dq.back().second:INT_INF);
			if(lft < k-1 && (h_segs[lft+1][k-1].empty() || h_segs[lft+1][k-1].back() != i))
				h_segs[lft+1][k-1].pb(i); //rows[i].pb(mp(lft+1,k-1));
			while(dq.size() && dq.back().first == arr[i][k]) dq.pop_back();
			dq.pb(mp(arr[i][k],k));
		}
		while(dq.size()) dq.pop_back();
		for(int k=num_cols; k>=1; k--){
			while(dq.size() && dq.back().first < arr[i][k]) dq.pop_back();
			int rgt = (dq.size()?dq.back().second:-INT_INF);
			if(rgt > k+1 && (h_segs[k+1][rgt-1].empty() || h_segs[k+1][rgt-1].back() != i))
				h_segs[k+1][rgt-1].pb(i); //rows[i].pb(mp(k+1,rgt-1));
			while(dq.size() && dq.back().first == arr[i][k]) dq.pop_back();
			dq.pb(mp(arr[i][k],k));
		}
	}
}

inline void init_cols(){
	for(int i=2; i<num_cols; i++){
		deque<pii> dq;
		for(int k=1; k<=num_rows; k++){
			while(dq.size() && dq.back().first < arr[k][i]) dq.pop_back();
			int lft = (dq.size()?dq.back().second:INT_INF);
			if(lft < k-1 && (v_segs[lft+1][k-1].empty() || v_segs[lft+1][k-1].back() != i))
				v_segs[lft+1][k-1].pb(i); //cols[i].pb(mp(lft+1,k-1));
			while(dq.size() && dq.back().first == arr[k][i]) dq.pop_back();
			dq.pb(mp(arr[k][i],k));
		}
		while(dq.size()) dq.pop_back();
		for(int k=num_rows; k>=1; k--){
			while(dq.size() && dq.back().first < arr[k][i]) dq.pop_back();
			int rgt = (dq.size()?dq.back().second:-INT_INF);
			if(rgt > k+1 && (v_segs[k+1][rgt-1].empty() || v_segs[k+1][rgt-1].back() != i))
				v_segs[k+1][rgt-1].pb(i); //cols[i].pb(mp(k+1,rgt-1));
			while(dq.size() && dq.back().first == arr[k][i]) dq.pop_back();
			dq.pb(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++){
			vector<int> &nums = h_segs[l][r];
			if(!nums.size()) continue;
//			sort(all(nums)); complete_unique(nums);
			int lst = 0;
			for(int i=1; i<nums.size(); i++){
				if(nums[i] == nums[i-1]+1) continue;
				for(int k=nums[lst]; k<=nums[i-1]; k++)
					row_dp[k][l].pb(mp(nums[i-1]-k+1,r));
				lst = i;
			}
			for(int k=nums[lst]; k<=nums.back(); k++)
				row_dp[k][l].pb(mp(nums.back()-k+1,r));
			nums.clear();
		}
	}
}

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++){
			vector<int> &nums = v_segs[l][r];
			if(!nums.size()) continue;
//			sort(all(nums)); complete_unique(nums);
			int lst = 0;
			for(int i=1; i<nums.size(); i++){
				if(nums[i] == nums[i-1]+1) continue;
				for(int k=nums[lst]; k<=nums[i-1]; k++)
					col_dp[l][k].pb(mp(r,nums[i-1]));
				lst = i;
			}
			for(int k=nums[lst]; k<=nums.back(); k++)
				col_dp[l][k].pb(mp(r,nums.back()));
			nums.clear();
		}
	}
}

ll count_rectangles(vector<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(); init_cols();
	calc_hor_dp(); calc_col_dp();
	for(int i=2; i<num_rows; i++){
		for(int k=2; k<num_cols; k++){
			sort(all(row_dp[i][k]));
			sort(all(col_dp[i][k]));
			int ptr = 0, res = 0, cnt = 0;
			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);
					ptr++, cnt++;
				}
				res+=cnt-query(row_dp[i][k][v].second-k);
			}
			while(ptr--){
				if(ptr == -1) break;
				update(col_dp[i][k][ptr].second-k+1,-1);
			}
			ans+=res;
		}
	}
	return ans;
}

Compilation message

rect.cpp: In function 'void calc_hor_dp()':
rect.cpp:128:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=1; i<nums.size(); i++){
                 ~^~~~~~~~~~~~
rect.cpp: In function 'void calc_col_dp()':
rect.cpp:156:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=1; i<nums.size(); i++){
                 ~^~~~~~~~~~~~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:171:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<a.size(); i++)
               ~^~~~~~~~~
rect.cpp:172:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0; k<a[i].size(); k++)
                ~^~~~~~~~~~~~
rect.cpp:181:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int v=0; v<row_dp[i][k].size(); v++){
                 ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:183: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 533 ms 589748 KB Output is correct
2 Correct 534 ms 590200 KB Output is correct
3 Correct 536 ms 590000 KB Output is correct
4 Correct 529 ms 589944 KB Output is correct
5 Correct 534 ms 590024 KB Output is correct
6 Correct 536 ms 590124 KB Output is correct
7 Correct 537 ms 589960 KB Output is correct
8 Correct 532 ms 589876 KB Output is correct
9 Correct 534 ms 589872 KB Output is correct
10 Correct 582 ms 590052 KB Output is correct
11 Correct 535 ms 589936 KB Output is correct
12 Correct 535 ms 589916 KB Output is correct
13 Correct 533 ms 589696 KB Output is correct
14 Correct 630 ms 589788 KB Output is correct
15 Correct 535 ms 589892 KB Output is correct
16 Correct 554 ms 589756 KB Output is correct
17 Correct 543 ms 589704 KB Output is correct
18 Correct 586 ms 589944 KB Output is correct
19 Correct 599 ms 590068 KB Output is correct
20 Correct 536 ms 589984 KB Output is correct
21 Correct 553 ms 590028 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 589748 KB Output is correct
2 Correct 534 ms 590200 KB Output is correct
3 Correct 536 ms 590000 KB Output is correct
4 Correct 529 ms 589944 KB Output is correct
5 Correct 534 ms 590024 KB Output is correct
6 Correct 536 ms 590124 KB Output is correct
7 Correct 537 ms 589960 KB Output is correct
8 Correct 532 ms 589876 KB Output is correct
9 Correct 534 ms 589872 KB Output is correct
10 Correct 582 ms 590052 KB Output is correct
11 Correct 535 ms 589936 KB Output is correct
12 Correct 535 ms 589916 KB Output is correct
13 Correct 533 ms 589696 KB Output is correct
14 Correct 630 ms 589788 KB Output is correct
15 Correct 535 ms 589892 KB Output is correct
16 Correct 554 ms 589756 KB Output is correct
17 Correct 543 ms 590688 KB Output is correct
18 Correct 537 ms 590808 KB Output is correct
19 Correct 533 ms 590732 KB Output is correct
20 Correct 533 ms 590328 KB Output is correct
21 Correct 530 ms 590652 KB Output is correct
22 Correct 536 ms 590572 KB Output is correct
23 Correct 534 ms 590456 KB Output is correct
24 Correct 532 ms 590216 KB Output is correct
25 Correct 543 ms 589704 KB Output is correct
26 Correct 586 ms 589944 KB Output is correct
27 Correct 599 ms 590068 KB Output is correct
28 Correct 536 ms 589984 KB Output is correct
29 Correct 553 ms 590028 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 589748 KB Output is correct
2 Correct 534 ms 590200 KB Output is correct
3 Correct 536 ms 590000 KB Output is correct
4 Correct 529 ms 589944 KB Output is correct
5 Correct 534 ms 590024 KB Output is correct
6 Correct 536 ms 590124 KB Output is correct
7 Correct 537 ms 589960 KB Output is correct
8 Correct 532 ms 589876 KB Output is correct
9 Correct 534 ms 589872 KB Output is correct
10 Correct 582 ms 590052 KB Output is correct
11 Correct 535 ms 589936 KB Output is correct
12 Correct 535 ms 589916 KB Output is correct
13 Correct 533 ms 589696 KB Output is correct
14 Correct 630 ms 589788 KB Output is correct
15 Correct 535 ms 589892 KB Output is correct
16 Correct 554 ms 589756 KB Output is correct
17 Correct 543 ms 590688 KB Output is correct
18 Correct 537 ms 590808 KB Output is correct
19 Correct 533 ms 590732 KB Output is correct
20 Correct 533 ms 590328 KB Output is correct
21 Correct 530 ms 590652 KB Output is correct
22 Correct 536 ms 590572 KB Output is correct
23 Correct 534 ms 590456 KB Output is correct
24 Correct 532 ms 590216 KB Output is correct
25 Correct 549 ms 594140 KB Output is correct
26 Correct 549 ms 594268 KB Output is correct
27 Correct 550 ms 594408 KB Output is correct
28 Correct 545 ms 592160 KB Output is correct
29 Correct 551 ms 593336 KB Output is correct
30 Correct 554 ms 593624 KB Output is correct
31 Correct 550 ms 593120 KB Output is correct
32 Correct 553 ms 593236 KB Output is correct
33 Correct 543 ms 589704 KB Output is correct
34 Correct 586 ms 589944 KB Output is correct
35 Correct 599 ms 590068 KB Output is correct
36 Correct 536 ms 589984 KB Output is correct
37 Correct 553 ms 590028 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 589748 KB Output is correct
2 Correct 534 ms 590200 KB Output is correct
3 Correct 536 ms 590000 KB Output is correct
4 Correct 529 ms 589944 KB Output is correct
5 Correct 534 ms 590024 KB Output is correct
6 Correct 536 ms 590124 KB Output is correct
7 Correct 537 ms 589960 KB Output is correct
8 Correct 532 ms 589876 KB Output is correct
9 Correct 534 ms 589872 KB Output is correct
10 Correct 582 ms 590052 KB Output is correct
11 Correct 535 ms 589936 KB Output is correct
12 Correct 535 ms 589916 KB Output is correct
13 Correct 533 ms 589696 KB Output is correct
14 Correct 630 ms 589788 KB Output is correct
15 Correct 535 ms 589892 KB Output is correct
16 Correct 554 ms 589756 KB Output is correct
17 Correct 543 ms 590688 KB Output is correct
18 Correct 537 ms 590808 KB Output is correct
19 Correct 533 ms 590732 KB Output is correct
20 Correct 533 ms 590328 KB Output is correct
21 Correct 530 ms 590652 KB Output is correct
22 Correct 536 ms 590572 KB Output is correct
23 Correct 534 ms 590456 KB Output is correct
24 Correct 532 ms 590216 KB Output is correct
25 Correct 549 ms 594140 KB Output is correct
26 Correct 549 ms 594268 KB Output is correct
27 Correct 550 ms 594408 KB Output is correct
28 Correct 545 ms 592160 KB Output is correct
29 Correct 551 ms 593336 KB Output is correct
30 Correct 554 ms 593624 KB Output is correct
31 Correct 550 ms 593120 KB Output is correct
32 Correct 553 ms 593236 KB Output is correct
33 Correct 747 ms 630260 KB Output is correct
34 Correct 721 ms 625460 KB Output is correct
35 Correct 718 ms 625356 KB Output is correct
36 Correct 655 ms 620656 KB Output is correct
37 Correct 787 ms 636096 KB Output is correct
38 Correct 762 ms 635848 KB Output is correct
39 Correct 770 ms 635896 KB Output is correct
40 Correct 766 ms 633208 KB Output is correct
41 Correct 692 ms 608200 KB Output is correct
42 Correct 699 ms 611576 KB Output is correct
43 Correct 885 ms 623284 KB Output is correct
44 Correct 915 ms 624408 KB Output is correct
45 Correct 685 ms 608572 KB Output is correct
46 Correct 680 ms 607416 KB Output is correct
47 Correct 803 ms 621616 KB Output is correct
48 Correct 804 ms 622656 KB Output is correct
49 Correct 543 ms 589704 KB Output is correct
50 Correct 586 ms 589944 KB Output is correct
51 Correct 599 ms 590068 KB Output is correct
52 Correct 536 ms 589984 KB Output is correct
53 Correct 553 ms 590028 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 590344 KB Output is correct
2 Correct 541 ms 590200 KB Output is correct
3 Correct 544 ms 589836 KB Output is correct
4 Correct 534 ms 589720 KB Output is correct
5 Correct 542 ms 590072 KB Output is correct
6 Correct 556 ms 590028 KB Output is correct
7 Correct 544 ms 590076 KB Output is correct
8 Correct 542 ms 590212 KB Output is correct
9 Correct 548 ms 590004 KB Output is correct
10 Correct 581 ms 590016 KB Output is correct
11 Correct 564 ms 589900 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 589776 KB Output is correct
2 Correct 1415 ms 682388 KB Output is correct
3 Correct 2601 ms 786408 KB Output is correct
4 Correct 2734 ms 787872 KB Output is correct
5 Correct 2654 ms 788260 KB Output is correct
6 Correct 843 ms 628812 KB Output is correct
7 Correct 1167 ms 665128 KB Output is correct
8 Correct 1191 ms 669100 KB Output is correct
9 Correct 543 ms 589704 KB Output is correct
10 Correct 586 ms 589944 KB Output is correct
11 Correct 599 ms 590068 KB Output is correct
12 Correct 536 ms 589984 KB Output is correct
13 Correct 553 ms 590028 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 589748 KB Output is correct
2 Correct 534 ms 590200 KB Output is correct
3 Correct 536 ms 590000 KB Output is correct
4 Correct 529 ms 589944 KB Output is correct
5 Correct 534 ms 590024 KB Output is correct
6 Correct 536 ms 590124 KB Output is correct
7 Correct 537 ms 589960 KB Output is correct
8 Correct 532 ms 589876 KB Output is correct
9 Correct 534 ms 589872 KB Output is correct
10 Correct 582 ms 590052 KB Output is correct
11 Correct 535 ms 589936 KB Output is correct
12 Correct 535 ms 589916 KB Output is correct
13 Correct 533 ms 589696 KB Output is correct
14 Correct 630 ms 589788 KB Output is correct
15 Correct 535 ms 589892 KB Output is correct
16 Correct 554 ms 589756 KB Output is correct
17 Correct 543 ms 590688 KB Output is correct
18 Correct 537 ms 590808 KB Output is correct
19 Correct 533 ms 590732 KB Output is correct
20 Correct 533 ms 590328 KB Output is correct
21 Correct 530 ms 590652 KB Output is correct
22 Correct 536 ms 590572 KB Output is correct
23 Correct 534 ms 590456 KB Output is correct
24 Correct 532 ms 590216 KB Output is correct
25 Correct 549 ms 594140 KB Output is correct
26 Correct 549 ms 594268 KB Output is correct
27 Correct 550 ms 594408 KB Output is correct
28 Correct 545 ms 592160 KB Output is correct
29 Correct 551 ms 593336 KB Output is correct
30 Correct 554 ms 593624 KB Output is correct
31 Correct 550 ms 593120 KB Output is correct
32 Correct 553 ms 593236 KB Output is correct
33 Correct 747 ms 630260 KB Output is correct
34 Correct 721 ms 625460 KB Output is correct
35 Correct 718 ms 625356 KB Output is correct
36 Correct 655 ms 620656 KB Output is correct
37 Correct 787 ms 636096 KB Output is correct
38 Correct 762 ms 635848 KB Output is correct
39 Correct 770 ms 635896 KB Output is correct
40 Correct 766 ms 633208 KB Output is correct
41 Correct 692 ms 608200 KB Output is correct
42 Correct 699 ms 611576 KB Output is correct
43 Correct 885 ms 623284 KB Output is correct
44 Correct 915 ms 624408 KB Output is correct
45 Correct 685 ms 608572 KB Output is correct
46 Correct 680 ms 607416 KB Output is correct
47 Correct 803 ms 621616 KB Output is correct
48 Correct 804 ms 622656 KB Output is correct
49 Correct 542 ms 590344 KB Output is correct
50 Correct 541 ms 590200 KB Output is correct
51 Correct 544 ms 589836 KB Output is correct
52 Correct 534 ms 589720 KB Output is correct
53 Correct 542 ms 590072 KB Output is correct
54 Correct 556 ms 590028 KB Output is correct
55 Correct 544 ms 590076 KB Output is correct
56 Correct 542 ms 590212 KB Output is correct
57 Correct 548 ms 590004 KB Output is correct
58 Correct 581 ms 590016 KB Output is correct
59 Correct 564 ms 589900 KB Output is correct
60 Correct 531 ms 589776 KB Output is correct
61 Correct 1415 ms 682388 KB Output is correct
62 Correct 2601 ms 786408 KB Output is correct
63 Correct 2734 ms 787872 KB Output is correct
64 Correct 2654 ms 788260 KB Output is correct
65 Correct 843 ms 628812 KB Output is correct
66 Correct 1167 ms 665128 KB Output is correct
67 Correct 1191 ms 669100 KB Output is correct
68 Runtime error 2793 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Halted 0 ms 0 KB -