oj.uz

Submission #723288

# Submission time Handle Problem Language Result Execution time Memory
723288 2023-04-13T13:54:44 Z myrcella Rectangles (IOI19_rect) C++17
100 / 100
 3234 ms 600740 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "rect.h"

int N,M;
const int maxn = 2555;
int grid[maxn][maxn];
vector <pair<pii,int> > row1[maxn];
vector <pii> row[maxn][maxn];
vector <pii> hi[maxn];
int tree[maxn][maxn];
stack <int> q;
int lft[maxn][maxn],rit[maxn][maxn];

void update(pii tmp,int val) {
	int pos = tmp.se;
	while (pos<maxn) {
		tree[tmp.fi][pos] += val;
		pos += lowbit(pos);
	}
	return;
}

int query(int id,int pos) {
	int ret = 0;
	while (pos) {
		ret += tree[id][pos];
		pos -= lowbit(pos);
	}
	return ret;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	N = SZ(a),M=SZ(a[0]);
	rep(i,0,N) rep(j,0,M) grid[i][j] = a[i][j];
	memset(lft,-1,sizeof(lft));memset(rit,-1,sizeof(rit));
	rep(i,1,N-1) {
		while (!q.empty()) q.pop();
		rep(j,0,M) {
			while (!q.empty() and a[i][q.top()]<a[i][j]) q.pop();
			if (!q.empty() and q.top()!=j-1) hi[i].pb({q.top(),j}),lft[i][j] = q.top();
			q.push(j);
		}
		while (!q.empty()) q.pop();
		for (int j = M-1;j>=0;j--) {
			while (!q.empty() and a[i][q.top()]<a[i][j]) q.pop();
			if (!q.empty() and q.top()!=j+1) hi[i].pb({j,q.top()}),rit[i][j] = q.top();
			q.push(j);
		}
	}
	rep(i,1,N-1) {
		for (auto it:hi[i]) {
			if (lft[i][it.se]!=it.fi and rit[i][it.fi]!=it.se) continue;
			if (lft[i][it.se]==it.fi) lft[i][it.se]=-1;
			if (rit[i][it.fi]==it.se) rit[i][it.fi] = -1;
			int cur = i+1;
			while (cur<N-1 and (lft[cur][it.se]==it.fi or rit[cur][it.fi]==it.se)) {
				if (lft[cur][it.se]==it.fi) lft[cur][it.se]=-1;
				if (rit[cur][it.fi]==it.se) rit[cur][it.fi] = -1;
				cur++;
			}
			rep(j,i,cur) row1[j].pb({{it.fi+1,it.se-1},cur-1});
		}
		while (!hi[i].empty()) hi[i].pop_back();
		sort(ALL(row1[i]));
	}
	memset(lft,-1,sizeof(lft));memset(rit,-1,sizeof(rit));
	rep(i,1,M-1) {
		while (!q.empty()) q.pop();
		rep(j,0,N) {
			while (!q.empty() and a[q.top()][i]<a[j][i]) q.pop();
			if (!q.empty() and q.top()!=j-1) hi[i].pb({q.top(),j}),lft[j][i] = q.top();
			q.push(j);
		}
		while (!q.empty()) q.pop();
		for (int j = N-1;j>=0;j--) {
			while (!q.empty() and a[q.top()][i]<a[j][i]) q.pop();
			if (!q.empty() and q.top()!=j+1) hi[i].pb({j,q.top()}),rit[j][i] = q.top();
			q.push(j);
		}
	}
	rep(i,1,M-1) {
		for (auto it:hi[i]) {
			if (lft[it.se][i]!=it.fi and rit[it.fi][i]!=it.se) continue;
			int cur = i+1;
			if (lft[it.se][i]==it.fi) lft[it.se][i] = -1;
			if (rit[it.fi][i]==it.se) rit[it.fi][i] = -1;
			while (cur<M-1 and (lft[it.se][cur]==it.fi or rit[it.fi][cur] == it.se)) {
				if (lft[it.se][cur]==it.fi) lft[it.se][cur] = -1;
				if (rit[it.fi][cur]==it.se) rit[it.fi][cur] = -1;
				cur++;
			}
			rep(j,i,cur) row[(it).fi+1][i].pb({j,(it).se-1});
		}
	}
	ll ans = 0;
	rep(i,1,N-1) {
		int cur = 1;
		vector <pii> tmp;
		for (auto it:row1[i]) {
			while (cur<=it.fi.fi) {
				for (auto itt:row[i][cur]) update(itt,1),tmp.pb(itt);
				cur++;
			}
			ans += query(it.fi.se,it.se);
//			cout<<it.fi.fi<<" "<<it.fi.se<<" "<<i<<" "<<it.se<<" "<<ans<<endl;
		}
		while (!tmp.empty()) update(tmp.back(),-1),tmp.pop_back();
	}
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 204748 KB Output is correct
2 Correct 98 ms 205272 KB Output is correct
3 Correct 97 ms 205212 KB Output is correct
4 Correct 100 ms 205260 KB Output is correct
5 Correct 109 ms 204928 KB Output is correct
6 Correct 94 ms 205296 KB Output is correct
7 Correct 96 ms 205004 KB Output is correct
8 Correct 97 ms 205132 KB Output is correct
9 Correct 96 ms 205232 KB Output is correct
10 Correct 94 ms 205132 KB Output is correct
11 Correct 96 ms 205312 KB Output is correct
12 Correct 99 ms 205160 KB Output is correct
13 Correct 97 ms 204764 KB Output is correct
14 Correct 102 ms 204800 KB Output is correct
15 Correct 99 ms 204740 KB Output is correct
16 Correct 97 ms 204748 KB Output is correct
17 Correct 98 ms 204792 KB Output is correct
18 Correct 98 ms 204788 KB Output is correct
19 Correct 96 ms 205240 KB Output is correct
20 Correct 107 ms 204888 KB Output is correct
21 Correct 100 ms 204836 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 204748 KB Output is correct
2 Correct 98 ms 205272 KB Output is correct
3 Correct 97 ms 205212 KB Output is correct
4 Correct 100 ms 205260 KB Output is correct
5 Correct 109 ms 204928 KB Output is correct
6 Correct 94 ms 205296 KB Output is correct
7 Correct 96 ms 205004 KB Output is correct
8 Correct 97 ms 205132 KB Output is correct
9 Correct 96 ms 205232 KB Output is correct
10 Correct 94 ms 205132 KB Output is correct
11 Correct 96 ms 205312 KB Output is correct
12 Correct 99 ms 205160 KB Output is correct
13 Correct 97 ms 204764 KB Output is correct
14 Correct 102 ms 204800 KB Output is correct
15 Correct 99 ms 204740 KB Output is correct
16 Correct 97 ms 204748 KB Output is correct
17 Correct 98 ms 204792 KB Output is correct
18 Correct 98 ms 204788 KB Output is correct
19 Correct 96 ms 205240 KB Output is correct
20 Correct 107 ms 204888 KB Output is correct
21 Correct 100 ms 204836 KB Output is correct
22 Correct 103 ms 206412 KB Output is correct
23 Correct 100 ms 206308 KB Output is correct
24 Correct 110 ms 206284 KB Output is correct
25 Correct 103 ms 206128 KB Output is correct
26 Correct 104 ms 206248 KB Output is correct
27 Correct 125 ms 206280 KB Output is correct
28 Correct 98 ms 206308 KB Output is correct
29 Correct 105 ms 205712 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 204748 KB Output is correct
2 Correct 98 ms 205272 KB Output is correct
3 Correct 97 ms 205212 KB Output is correct
4 Correct 100 ms 205260 KB Output is correct
5 Correct 109 ms 204928 KB Output is correct
6 Correct 94 ms 205296 KB Output is correct
7 Correct 96 ms 205004 KB Output is correct
8 Correct 97 ms 205132 KB Output is correct
9 Correct 96 ms 205232 KB Output is correct
10 Correct 94 ms 205132 KB Output is correct
11 Correct 96 ms 205312 KB Output is correct
12 Correct 99 ms 205160 KB Output is correct
13 Correct 97 ms 204764 KB Output is correct
14 Correct 102 ms 204800 KB Output is correct
15 Correct 99 ms 204740 KB Output is correct
16 Correct 97 ms 204748 KB Output is correct
17 Correct 103 ms 206412 KB Output is correct
18 Correct 100 ms 206308 KB Output is correct
19 Correct 110 ms 206284 KB Output is correct
20 Correct 103 ms 206128 KB Output is correct
21 Correct 104 ms 206248 KB Output is correct
22 Correct 125 ms 206280 KB Output is correct
23 Correct 98 ms 206308 KB Output is correct
24 Correct 105 ms 205712 KB Output is correct
25 Correct 98 ms 204792 KB Output is correct
26 Correct 98 ms 204788 KB Output is correct
27 Correct 96 ms 205240 KB Output is correct
28 Correct 107 ms 204888 KB Output is correct
29 Correct 100 ms 204836 KB Output is correct
30 Correct 108 ms 209612 KB Output is correct
31 Correct 112 ms 209612 KB Output is correct
32 Correct 104 ms 209604 KB Output is correct
33 Correct 110 ms 209188 KB Output is correct
34 Correct 120 ms 210012 KB Output is correct
35 Correct 125 ms 209936 KB Output is correct
36 Correct 111 ms 209864 KB Output is correct
37 Correct 117 ms 209848 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 204748 KB Output is correct
2 Correct 98 ms 205272 KB Output is correct
3 Correct 97 ms 205212 KB Output is correct
4 Correct 100 ms 205260 KB Output is correct
5 Correct 109 ms 204928 KB Output is correct
6 Correct 94 ms 205296 KB Output is correct
7 Correct 96 ms 205004 KB Output is correct
8 Correct 97 ms 205132 KB Output is correct
9 Correct 96 ms 205232 KB Output is correct
10 Correct 94 ms 205132 KB Output is correct
11 Correct 96 ms 205312 KB Output is correct
12 Correct 99 ms 205160 KB Output is correct
13 Correct 97 ms 204764 KB Output is correct
14 Correct 102 ms 204800 KB Output is correct
15 Correct 99 ms 204740 KB Output is correct
16 Correct 97 ms 204748 KB Output is correct
17 Correct 103 ms 206412 KB Output is correct
18 Correct 100 ms 206308 KB Output is correct
19 Correct 110 ms 206284 KB Output is correct
20 Correct 103 ms 206128 KB Output is correct
21 Correct 104 ms 206248 KB Output is correct
22 Correct 125 ms 206280 KB Output is correct
23 Correct 98 ms 206308 KB Output is correct
24 Correct 105 ms 205712 KB Output is correct
25 Correct 108 ms 209612 KB Output is correct
26 Correct 112 ms 209612 KB Output is correct
27 Correct 104 ms 209604 KB Output is correct
28 Correct 110 ms 209188 KB Output is correct
29 Correct 120 ms 210012 KB Output is correct
30 Correct 125 ms 209936 KB Output is correct
31 Correct 111 ms 209864 KB Output is correct
32 Correct 117 ms 209848 KB Output is correct
33 Correct 98 ms 204792 KB Output is correct
34 Correct 98 ms 204788 KB Output is correct
35 Correct 96 ms 205240 KB Output is correct
36 Correct 107 ms 204888 KB Output is correct
37 Correct 100 ms 204836 KB Output is correct
38 Correct 168 ms 235216 KB Output is correct
39 Correct 191 ms 236688 KB Output is correct
40 Correct 150 ms 232012 KB Output is correct
41 Correct 155 ms 230520 KB Output is correct
42 Correct 181 ms 239724 KB Output is correct
43 Correct 184 ms 240204 KB Output is correct
44 Correct 190 ms 240204 KB Output is correct
45 Correct 192 ms 238796 KB Output is correct
46 Correct 171 ms 229428 KB Output is correct
47 Correct 198 ms 232484 KB Output is correct
48 Correct 282 ms 243148 KB Output is correct
49 Correct 290 ms 243340 KB Output is correct
50 Correct 204 ms 227096 KB Output is correct
51 Correct 197 ms 229240 KB Output is correct
52 Correct 288 ms 241976 KB Output is correct
53 Correct 265 ms 241864 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 230084 KB Output is correct
2 Correct 112 ms 226296 KB Output is correct
3 Correct 98 ms 204812 KB Output is correct
4 Correct 100 ms 204784 KB Output is correct
5 Correct 103 ms 214700 KB Output is correct
6 Correct 123 ms 214460 KB Output is correct
7 Correct 105 ms 214220 KB Output is correct
8 Correct 105 ms 213548 KB Output is correct
9 Correct 101 ms 213068 KB Output is correct
10 Correct 99 ms 204832 KB Output is correct
11 Correct 107 ms 204920 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 204792 KB Output is correct
2 Correct 98 ms 204788 KB Output is correct
3 Correct 96 ms 205240 KB Output is correct
4 Correct 107 ms 204888 KB Output is correct
5 Correct 100 ms 204836 KB Output is correct
6 Correct 99 ms 204912 KB Output is correct
7 Correct 601 ms 321812 KB Output is correct
8 Correct 1270 ms 411524 KB Output is correct
9 Correct 1272 ms 412176 KB Output is correct
10 Correct 1299 ms 412288 KB Output is correct
11 Correct 219 ms 241996 KB Output is correct
12 Correct 356 ms 276484 KB Output is correct
13 Correct 374 ms 279628 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 204748 KB Output is correct
2 Correct 98 ms 205272 KB Output is correct
3 Correct 97 ms 205212 KB Output is correct
4 Correct 100 ms 205260 KB Output is correct
5 Correct 109 ms 204928 KB Output is correct
6 Correct 94 ms 205296 KB Output is correct
7 Correct 96 ms 205004 KB Output is correct
8 Correct 97 ms 205132 KB Output is correct
9 Correct 96 ms 205232 KB Output is correct
10 Correct 94 ms 205132 KB Output is correct
11 Correct 96 ms 205312 KB Output is correct
12 Correct 99 ms 205160 KB Output is correct
13 Correct 97 ms 204764 KB Output is correct
14 Correct 102 ms 204800 KB Output is correct
15 Correct 99 ms 204740 KB Output is correct
16 Correct 97 ms 204748 KB Output is correct
17 Correct 103 ms 206412 KB Output is correct
18 Correct 100 ms 206308 KB Output is correct
19 Correct 110 ms 206284 KB Output is correct
20 Correct 103 ms 206128 KB Output is correct
21 Correct 104 ms 206248 KB Output is correct
22 Correct 125 ms 206280 KB Output is correct
23 Correct 98 ms 206308 KB Output is correct
24 Correct 105 ms 205712 KB Output is correct
25 Correct 108 ms 209612 KB Output is correct
26 Correct 112 ms 209612 KB Output is correct
27 Correct 104 ms 209604 KB Output is correct
28 Correct 110 ms 209188 KB Output is correct
29 Correct 120 ms 210012 KB Output is correct
30 Correct 125 ms 209936 KB Output is correct
31 Correct 111 ms 209864 KB Output is correct
32 Correct 117 ms 209848 KB Output is correct
33 Correct 168 ms 235216 KB Output is correct
34 Correct 191 ms 236688 KB Output is correct
35 Correct 150 ms 232012 KB Output is correct
36 Correct 155 ms 230520 KB Output is correct
37 Correct 181 ms 239724 KB Output is correct
38 Correct 184 ms 240204 KB Output is correct
39 Correct 190 ms 240204 KB Output is correct
40 Correct 192 ms 238796 KB Output is correct
41 Correct 171 ms 229428 KB Output is correct
42 Correct 198 ms 232484 KB Output is correct
43 Correct 282 ms 243148 KB Output is correct
44 Correct 290 ms 243340 KB Output is correct
45 Correct 204 ms 227096 KB Output is correct
46 Correct 197 ms 229240 KB Output is correct
47 Correct 288 ms 241976 KB Output is correct
48 Correct 265 ms 241864 KB Output is correct
49 Correct 116 ms 230084 KB Output is correct
50 Correct 112 ms 226296 KB Output is correct
51 Correct 98 ms 204812 KB Output is correct
52 Correct 100 ms 204784 KB Output is correct
53 Correct 103 ms 214700 KB Output is correct
54 Correct 123 ms 214460 KB Output is correct
55 Correct 105 ms 214220 KB Output is correct
56 Correct 105 ms 213548 KB Output is correct
57 Correct 101 ms 213068 KB Output is correct
58 Correct 99 ms 204832 KB Output is correct
59 Correct 107 ms 204920 KB Output is correct
60 Correct 99 ms 204912 KB Output is correct
61 Correct 601 ms 321812 KB Output is correct
62 Correct 1270 ms 411524 KB Output is correct
63 Correct 1272 ms 412176 KB Output is correct
64 Correct 1299 ms 412288 KB Output is correct
65 Correct 219 ms 241996 KB Output is correct
66 Correct 356 ms 276484 KB Output is correct
67 Correct 374 ms 279628 KB Output is correct
68 Correct 98 ms 204792 KB Output is correct
69 Correct 98 ms 204788 KB Output is correct
70 Correct 96 ms 205240 KB Output is correct
71 Correct 107 ms 204888 KB Output is correct
72 Correct 100 ms 204836 KB Output is correct
73 Correct 1091 ms 469088 KB Output is correct
74 Correct 1511 ms 483256 KB Output is correct
75 Correct 782 ms 419076 KB Output is correct
76 Correct 840 ms 404544 KB Output is correct
77 Correct 1427 ms 509196 KB Output is correct
78 Correct 1798 ms 451544 KB Output is correct
79 Correct 1731 ms 480740 KB Output is correct
80 Correct 2745 ms 573444 KB Output is correct
81 Correct 1803 ms 467880 KB Output is correct
82 Correct 2282 ms 536808 KB Output is correct
83 Correct 3234 ms 600740 KB Output is correct
84 Correct 1706 ms 447448 KB Output is correct
85 Correct 2809 ms 584060 KB Output is correct
86 Correct 2698 ms 573960 KB Output is correct
87 Correct 939 ms 448036 KB Output is correct
88 Correct 1554 ms 557000 KB Output is correct
89 Correct 1491 ms 557080 KB Output is correct
90 Correct 1366 ms 557192 KB Output is correct