# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
836514 |
2023-08-24T12:10:19 Z |
Rafi22 |
Rectangles (IOI19_rect) |
C++14 |
|
4804 ms |
496324 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;
const int N=2507,pot=1<<12;
vector<int>V[N][N];
int U[N][2*pot+7];
int D[N][2*pot+7];
int n,m;
int queU(int v,int a,int b,int l,int r,int i)
{
if(a<=l&&b>=r) return U[i][v];
if(r<a||l>b) return -1;
return max(queU(2*v,a,b,l,(l+r)/2,i),queU(2*v+1,a,b,(l+r)/2+1,r,i));
}
int queD(int v,int a,int b,int l,int r,int i)
{
if(a<=l&&b>=r) return D[i][v];
if(r<a||l>b) return n;
return min(queD(2*v,a,b,l,(l+r)/2,i),queD(2*v+1,a,b,(l+r)/2+1,r,i));
}
int BIT[N];
int que(int x)
{
int s=0;
for (;x;x-=x&-x) s+=BIT[x];
return s;
}
void ins(int x,int s) {
for (;x<N;x+=x&-x) BIT[x]+=s;
}
bool alive[N];
ll count_rectangles(vector<vector<int>>a)
{
ll ans=0;
n=sz(a),m=sz(a[0]);
for(int i=1;i<n-1;i++)
{
deque<pair<int,int>>Q;
Q.pb({a[i][0],0});
for(int j=1;j<m;j++)
{
while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back();
if(sz(Q)>0) V[Q.back().nd+1][j-1].pb(i);
Q.pb({a[i][j],j});
}
Q.clear();
Q.pb({a[i][m-1],m-1});
for(int j=m-2;j>=0;j--)
{
while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back();
if(sz(Q)>0) V[j+1][Q.back().nd-1].pb(i);
Q.pb({a[i][j],j});
}
}
for(int i=0;i<n;i++)
{
for(int j=1;j<2*pot;j++)
{
U[i][j]=-1;
D[i][j]=n;
}
}
for(int j=0;j<m;j++)
{
deque<pair<int,int>>Q;
Q.pb({a[0][j],0});
for(int i=1;i<n;i++)
{
while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back();
if(sz(Q)>0) U[i][j+pot]=Q.back().nd;
Q.pb({a[i][j],i});
}
Q.clear();
Q.pb({a[n-1][j],n-1});
for(int i=n-2;i>=0;i--)
{
while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back();
if(sz(Q)>0) D[i][j+pot]=Q.back().nd;;
Q.pb({a[i][j],i});
}
}
for(int i=0;i<n;i++)
{
for(int j=pot-1;j>0;j--)
{
U[i][j]=max(U[i][2*j],U[i][2*j+1]);
D[i][j]=min(D[i][2*j],D[i][2*j+1]);
}
}
for(int i=0;i<m;i++)
{
for(int j=i;j<m;j++)
{
if(sz(V[i][j])==0) continue;
sort(all(V[i][j]));
int l=-2,p=-1;
priority_queue<pair<int,int>>Q;
for(auto x:V[i][j])
{
if(x==l) continue;
if(x!=l+1)
{
for(int y=p;y<l+1;y++)
{
if(alive[y])
{
ins(y+1,-1);
alive[y]=0;
}
}
p=x;
}
l=x;
ins(x+1,1);
alive[x]=1;
Q.push({-queD(1,i+1,j+1,1,pot,x-1),x});
while(sz(Q)>0&&-Q.top().st<=x)
{
if(alive[Q.top().nd])
{
ins(Q.top().nd+1,-1);
alive[Q.top().nd]=0;
}
Q.pop();
}
ans+=(ll)que(x+1)-que(queU(1,i+1,j+1,1,pot,x+1)+1);
}
for(int y=p;y<l+1;y++)
{
if(alive[y])
{
ins(y+1,-1);
alive[y]=0;
}
}
}
}
return ans;
}
/*
int main()
{
cout<<count_rectangles({
{4, 8, 7, 5, 6},
{7, 4, 10, 3, 5},
{9, 7, 20, 14, 2},
{9, 14, 7, 3, 6},
{5, 7, 5, 2, 7},
{4, 5, 13, 5, 6}})<<endl;
return 0;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
148248 KB |
Output is correct |
2 |
Correct |
68 ms |
149732 KB |
Output is correct |
3 |
Correct |
71 ms |
149836 KB |
Output is correct |
4 |
Correct |
66 ms |
149836 KB |
Output is correct |
5 |
Correct |
67 ms |
149844 KB |
Output is correct |
6 |
Correct |
67 ms |
149808 KB |
Output is correct |
7 |
Correct |
67 ms |
149836 KB |
Output is correct |
8 |
Correct |
65 ms |
148640 KB |
Output is correct |
9 |
Correct |
66 ms |
149836 KB |
Output is correct |
10 |
Correct |
71 ms |
149836 KB |
Output is correct |
11 |
Correct |
66 ms |
149780 KB |
Output is correct |
12 |
Correct |
67 ms |
149836 KB |
Output is correct |
13 |
Correct |
65 ms |
147916 KB |
Output is correct |
14 |
Correct |
66 ms |
148424 KB |
Output is correct |
15 |
Correct |
67 ms |
148428 KB |
Output is correct |
16 |
Correct |
66 ms |
148044 KB |
Output is correct |
17 |
Correct |
66 ms |
147916 KB |
Output is correct |
18 |
Correct |
64 ms |
147916 KB |
Output is correct |
19 |
Correct |
66 ms |
149836 KB |
Output is correct |
20 |
Correct |
72 ms |
149780 KB |
Output is correct |
21 |
Correct |
65 ms |
148448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
148248 KB |
Output is correct |
2 |
Correct |
68 ms |
149732 KB |
Output is correct |
3 |
Correct |
71 ms |
149836 KB |
Output is correct |
4 |
Correct |
66 ms |
149836 KB |
Output is correct |
5 |
Correct |
67 ms |
149844 KB |
Output is correct |
6 |
Correct |
67 ms |
149808 KB |
Output is correct |
7 |
Correct |
67 ms |
149836 KB |
Output is correct |
8 |
Correct |
65 ms |
148640 KB |
Output is correct |
9 |
Correct |
66 ms |
149836 KB |
Output is correct |
10 |
Correct |
71 ms |
149836 KB |
Output is correct |
11 |
Correct |
66 ms |
149780 KB |
Output is correct |
12 |
Correct |
67 ms |
149836 KB |
Output is correct |
13 |
Correct |
65 ms |
147916 KB |
Output is correct |
14 |
Correct |
66 ms |
148424 KB |
Output is correct |
15 |
Correct |
67 ms |
148428 KB |
Output is correct |
16 |
Correct |
66 ms |
148044 KB |
Output is correct |
17 |
Correct |
66 ms |
147916 KB |
Output is correct |
18 |
Correct |
64 ms |
147916 KB |
Output is correct |
19 |
Correct |
66 ms |
149836 KB |
Output is correct |
20 |
Correct |
72 ms |
149780 KB |
Output is correct |
21 |
Correct |
65 ms |
148448 KB |
Output is correct |
22 |
Correct |
69 ms |
153140 KB |
Output is correct |
23 |
Correct |
89 ms |
153140 KB |
Output is correct |
24 |
Correct |
71 ms |
153100 KB |
Output is correct |
25 |
Correct |
71 ms |
153164 KB |
Output is correct |
26 |
Correct |
72 ms |
153016 KB |
Output is correct |
27 |
Correct |
72 ms |
153164 KB |
Output is correct |
28 |
Correct |
70 ms |
153136 KB |
Output is correct |
29 |
Correct |
69 ms |
153036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
148248 KB |
Output is correct |
2 |
Correct |
68 ms |
149732 KB |
Output is correct |
3 |
Correct |
71 ms |
149836 KB |
Output is correct |
4 |
Correct |
66 ms |
149836 KB |
Output is correct |
5 |
Correct |
67 ms |
149844 KB |
Output is correct |
6 |
Correct |
67 ms |
149808 KB |
Output is correct |
7 |
Correct |
67 ms |
149836 KB |
Output is correct |
8 |
Correct |
65 ms |
148640 KB |
Output is correct |
9 |
Correct |
66 ms |
149836 KB |
Output is correct |
10 |
Correct |
71 ms |
149836 KB |
Output is correct |
11 |
Correct |
66 ms |
149780 KB |
Output is correct |
12 |
Correct |
67 ms |
149836 KB |
Output is correct |
13 |
Correct |
65 ms |
147916 KB |
Output is correct |
14 |
Correct |
66 ms |
148424 KB |
Output is correct |
15 |
Correct |
67 ms |
148428 KB |
Output is correct |
16 |
Correct |
66 ms |
148044 KB |
Output is correct |
17 |
Correct |
69 ms |
153140 KB |
Output is correct |
18 |
Correct |
89 ms |
153140 KB |
Output is correct |
19 |
Correct |
71 ms |
153100 KB |
Output is correct |
20 |
Correct |
71 ms |
153164 KB |
Output is correct |
21 |
Correct |
72 ms |
153016 KB |
Output is correct |
22 |
Correct |
72 ms |
153164 KB |
Output is correct |
23 |
Correct |
70 ms |
153136 KB |
Output is correct |
24 |
Correct |
69 ms |
153036 KB |
Output is correct |
25 |
Correct |
66 ms |
147916 KB |
Output is correct |
26 |
Correct |
64 ms |
147916 KB |
Output is correct |
27 |
Correct |
66 ms |
149836 KB |
Output is correct |
28 |
Correct |
72 ms |
149780 KB |
Output is correct |
29 |
Correct |
65 ms |
148448 KB |
Output is correct |
30 |
Correct |
88 ms |
161484 KB |
Output is correct |
31 |
Correct |
88 ms |
161488 KB |
Output is correct |
32 |
Correct |
86 ms |
161500 KB |
Output is correct |
33 |
Correct |
81 ms |
161612 KB |
Output is correct |
34 |
Correct |
88 ms |
161540 KB |
Output is correct |
35 |
Correct |
88 ms |
161600 KB |
Output is correct |
36 |
Correct |
88 ms |
161512 KB |
Output is correct |
37 |
Correct |
88 ms |
161376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
148248 KB |
Output is correct |
2 |
Correct |
68 ms |
149732 KB |
Output is correct |
3 |
Correct |
71 ms |
149836 KB |
Output is correct |
4 |
Correct |
66 ms |
149836 KB |
Output is correct |
5 |
Correct |
67 ms |
149844 KB |
Output is correct |
6 |
Correct |
67 ms |
149808 KB |
Output is correct |
7 |
Correct |
67 ms |
149836 KB |
Output is correct |
8 |
Correct |
65 ms |
148640 KB |
Output is correct |
9 |
Correct |
66 ms |
149836 KB |
Output is correct |
10 |
Correct |
71 ms |
149836 KB |
Output is correct |
11 |
Correct |
66 ms |
149780 KB |
Output is correct |
12 |
Correct |
67 ms |
149836 KB |
Output is correct |
13 |
Correct |
65 ms |
147916 KB |
Output is correct |
14 |
Correct |
66 ms |
148424 KB |
Output is correct |
15 |
Correct |
67 ms |
148428 KB |
Output is correct |
16 |
Correct |
66 ms |
148044 KB |
Output is correct |
17 |
Correct |
69 ms |
153140 KB |
Output is correct |
18 |
Correct |
89 ms |
153140 KB |
Output is correct |
19 |
Correct |
71 ms |
153100 KB |
Output is correct |
20 |
Correct |
71 ms |
153164 KB |
Output is correct |
21 |
Correct |
72 ms |
153016 KB |
Output is correct |
22 |
Correct |
72 ms |
153164 KB |
Output is correct |
23 |
Correct |
70 ms |
153136 KB |
Output is correct |
24 |
Correct |
69 ms |
153036 KB |
Output is correct |
25 |
Correct |
88 ms |
161484 KB |
Output is correct |
26 |
Correct |
88 ms |
161488 KB |
Output is correct |
27 |
Correct |
86 ms |
161500 KB |
Output is correct |
28 |
Correct |
81 ms |
161612 KB |
Output is correct |
29 |
Correct |
88 ms |
161540 KB |
Output is correct |
30 |
Correct |
88 ms |
161600 KB |
Output is correct |
31 |
Correct |
88 ms |
161512 KB |
Output is correct |
32 |
Correct |
88 ms |
161376 KB |
Output is correct |
33 |
Correct |
66 ms |
147916 KB |
Output is correct |
34 |
Correct |
64 ms |
147916 KB |
Output is correct |
35 |
Correct |
66 ms |
149836 KB |
Output is correct |
36 |
Correct |
72 ms |
149780 KB |
Output is correct |
37 |
Correct |
65 ms |
148448 KB |
Output is correct |
38 |
Correct |
265 ms |
207180 KB |
Output is correct |
39 |
Correct |
218 ms |
207184 KB |
Output is correct |
40 |
Correct |
269 ms |
207176 KB |
Output is correct |
41 |
Correct |
218 ms |
207196 KB |
Output is correct |
42 |
Correct |
337 ms |
202412 KB |
Output is correct |
43 |
Correct |
337 ms |
202456 KB |
Output is correct |
44 |
Correct |
348 ms |
202316 KB |
Output is correct |
45 |
Correct |
318 ms |
199240 KB |
Output is correct |
46 |
Correct |
179 ms |
204332 KB |
Output is correct |
47 |
Correct |
204 ms |
201292 KB |
Output is correct |
48 |
Correct |
306 ms |
202700 KB |
Output is correct |
49 |
Correct |
310 ms |
202700 KB |
Output is correct |
50 |
Correct |
197 ms |
197792 KB |
Output is correct |
51 |
Correct |
187 ms |
175496 KB |
Output is correct |
52 |
Correct |
294 ms |
202212 KB |
Output is correct |
53 |
Correct |
294 ms |
202148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
148300 KB |
Output is correct |
2 |
Correct |
74 ms |
148344 KB |
Output is correct |
3 |
Correct |
76 ms |
148212 KB |
Output is correct |
4 |
Correct |
69 ms |
148168 KB |
Output is correct |
5 |
Correct |
76 ms |
148216 KB |
Output is correct |
6 |
Correct |
77 ms |
148300 KB |
Output is correct |
7 |
Correct |
77 ms |
148208 KB |
Output is correct |
8 |
Correct |
77 ms |
148300 KB |
Output is correct |
9 |
Correct |
76 ms |
148176 KB |
Output is correct |
10 |
Correct |
77 ms |
147916 KB |
Output is correct |
11 |
Correct |
74 ms |
148028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
147916 KB |
Output is correct |
2 |
Correct |
64 ms |
147916 KB |
Output is correct |
3 |
Correct |
66 ms |
149836 KB |
Output is correct |
4 |
Correct |
72 ms |
149780 KB |
Output is correct |
5 |
Correct |
65 ms |
148448 KB |
Output is correct |
6 |
Correct |
66 ms |
148428 KB |
Output is correct |
7 |
Correct |
961 ms |
278564 KB |
Output is correct |
8 |
Correct |
1844 ms |
418048 KB |
Output is correct |
9 |
Correct |
1872 ms |
421884 KB |
Output is correct |
10 |
Correct |
1873 ms |
422348 KB |
Output is correct |
11 |
Correct |
602 ms |
292556 KB |
Output is correct |
12 |
Correct |
1155 ms |
423260 KB |
Output is correct |
13 |
Correct |
1205 ms |
430424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
148248 KB |
Output is correct |
2 |
Correct |
68 ms |
149732 KB |
Output is correct |
3 |
Correct |
71 ms |
149836 KB |
Output is correct |
4 |
Correct |
66 ms |
149836 KB |
Output is correct |
5 |
Correct |
67 ms |
149844 KB |
Output is correct |
6 |
Correct |
67 ms |
149808 KB |
Output is correct |
7 |
Correct |
67 ms |
149836 KB |
Output is correct |
8 |
Correct |
65 ms |
148640 KB |
Output is correct |
9 |
Correct |
66 ms |
149836 KB |
Output is correct |
10 |
Correct |
71 ms |
149836 KB |
Output is correct |
11 |
Correct |
66 ms |
149780 KB |
Output is correct |
12 |
Correct |
67 ms |
149836 KB |
Output is correct |
13 |
Correct |
65 ms |
147916 KB |
Output is correct |
14 |
Correct |
66 ms |
148424 KB |
Output is correct |
15 |
Correct |
67 ms |
148428 KB |
Output is correct |
16 |
Correct |
66 ms |
148044 KB |
Output is correct |
17 |
Correct |
69 ms |
153140 KB |
Output is correct |
18 |
Correct |
89 ms |
153140 KB |
Output is correct |
19 |
Correct |
71 ms |
153100 KB |
Output is correct |
20 |
Correct |
71 ms |
153164 KB |
Output is correct |
21 |
Correct |
72 ms |
153016 KB |
Output is correct |
22 |
Correct |
72 ms |
153164 KB |
Output is correct |
23 |
Correct |
70 ms |
153136 KB |
Output is correct |
24 |
Correct |
69 ms |
153036 KB |
Output is correct |
25 |
Correct |
88 ms |
161484 KB |
Output is correct |
26 |
Correct |
88 ms |
161488 KB |
Output is correct |
27 |
Correct |
86 ms |
161500 KB |
Output is correct |
28 |
Correct |
81 ms |
161612 KB |
Output is correct |
29 |
Correct |
88 ms |
161540 KB |
Output is correct |
30 |
Correct |
88 ms |
161600 KB |
Output is correct |
31 |
Correct |
88 ms |
161512 KB |
Output is correct |
32 |
Correct |
88 ms |
161376 KB |
Output is correct |
33 |
Correct |
265 ms |
207180 KB |
Output is correct |
34 |
Correct |
218 ms |
207184 KB |
Output is correct |
35 |
Correct |
269 ms |
207176 KB |
Output is correct |
36 |
Correct |
218 ms |
207196 KB |
Output is correct |
37 |
Correct |
337 ms |
202412 KB |
Output is correct |
38 |
Correct |
337 ms |
202456 KB |
Output is correct |
39 |
Correct |
348 ms |
202316 KB |
Output is correct |
40 |
Correct |
318 ms |
199240 KB |
Output is correct |
41 |
Correct |
179 ms |
204332 KB |
Output is correct |
42 |
Correct |
204 ms |
201292 KB |
Output is correct |
43 |
Correct |
306 ms |
202700 KB |
Output is correct |
44 |
Correct |
310 ms |
202700 KB |
Output is correct |
45 |
Correct |
197 ms |
197792 KB |
Output is correct |
46 |
Correct |
187 ms |
175496 KB |
Output is correct |
47 |
Correct |
294 ms |
202212 KB |
Output is correct |
48 |
Correct |
294 ms |
202148 KB |
Output is correct |
49 |
Correct |
78 ms |
148300 KB |
Output is correct |
50 |
Correct |
74 ms |
148344 KB |
Output is correct |
51 |
Correct |
76 ms |
148212 KB |
Output is correct |
52 |
Correct |
69 ms |
148168 KB |
Output is correct |
53 |
Correct |
76 ms |
148216 KB |
Output is correct |
54 |
Correct |
77 ms |
148300 KB |
Output is correct |
55 |
Correct |
77 ms |
148208 KB |
Output is correct |
56 |
Correct |
77 ms |
148300 KB |
Output is correct |
57 |
Correct |
76 ms |
148176 KB |
Output is correct |
58 |
Correct |
77 ms |
147916 KB |
Output is correct |
59 |
Correct |
74 ms |
148028 KB |
Output is correct |
60 |
Correct |
66 ms |
148428 KB |
Output is correct |
61 |
Correct |
961 ms |
278564 KB |
Output is correct |
62 |
Correct |
1844 ms |
418048 KB |
Output is correct |
63 |
Correct |
1872 ms |
421884 KB |
Output is correct |
64 |
Correct |
1873 ms |
422348 KB |
Output is correct |
65 |
Correct |
602 ms |
292556 KB |
Output is correct |
66 |
Correct |
1155 ms |
423260 KB |
Output is correct |
67 |
Correct |
1205 ms |
430424 KB |
Output is correct |
68 |
Correct |
66 ms |
147916 KB |
Output is correct |
69 |
Correct |
64 ms |
147916 KB |
Output is correct |
70 |
Correct |
66 ms |
149836 KB |
Output is correct |
71 |
Correct |
72 ms |
149780 KB |
Output is correct |
72 |
Correct |
65 ms |
148448 KB |
Output is correct |
73 |
Correct |
3199 ms |
496324 KB |
Output is correct |
74 |
Correct |
2189 ms |
496320 KB |
Output is correct |
75 |
Correct |
3242 ms |
495564 KB |
Output is correct |
76 |
Correct |
2246 ms |
495696 KB |
Output is correct |
77 |
Correct |
4804 ms |
435696 KB |
Output is correct |
78 |
Correct |
2253 ms |
319560 KB |
Output is correct |
79 |
Correct |
2305 ms |
386608 KB |
Output is correct |
80 |
Correct |
3543 ms |
435696 KB |
Output is correct |
81 |
Correct |
2238 ms |
320592 KB |
Output is correct |
82 |
Correct |
2851 ms |
409216 KB |
Output is correct |
83 |
Correct |
3621 ms |
432948 KB |
Output is correct |
84 |
Correct |
2045 ms |
313800 KB |
Output is correct |
85 |
Correct |
3403 ms |
431432 KB |
Output is correct |
86 |
Correct |
3315 ms |
424876 KB |
Output is correct |
87 |
Correct |
2916 ms |
385776 KB |
Output is correct |
88 |
Correct |
4254 ms |
435124 KB |
Output is correct |
89 |
Correct |
4589 ms |
434376 KB |
Output is correct |
90 |
Correct |
4430 ms |
434692 KB |
Output is correct |