# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
723288 |
2023-04-13T13:54:44 Z |
myrcella |
Rectangles (IOI19_rect) |
C++17 |
|
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;
}
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |