# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
213457 |
2020-03-25T21:04:35 Z |
Blagojce |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
343100 KB |
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define pb push_back
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 1e9 + 7;
ld const eps = 1e-13;
#include "rect.h"
int n, m;
int a[2500][2500];
vector<int> le[2500][2500];
vector<int> up[2500][2500];
void find_lefts(){
fr(i, 0, n){
fr(j, 0, m){
int MAX = 0;
for(int k = j - 1; k >= 0; k --){
if(j - k > 1 && MAX < a[i][j] && MAX < a[i][k]){
le[i][j].pb(k);
}
MAX = max(MAX, a[i][k]);
}
}
}
}
void find_ups(){
fr(i, 0, n){
fr(j, 0, m){
int MAX = 0;
for(int k = i - 1; k >= 0; k --){
if(i - k > 1 && MAX < a[i][j] && MAX < a[k][j]){
up[i][j].pb(k);
}
MAX = max(MAX, a[k][j]);
}
}
}
}
long long count_rectangles(std::vector<std::vector<int> > v) {
/*cin >> n >> m;
v.resize(n);
fr(i, 0, n){
v[i].resize(m);
fr(j, 0, m){
cin >> v[i][j];
}
}*/
n = v.size();
m = v[0].size();
fr(i, 0, n){
fr(j, 0, m){
a[i][j] = v[i][j];
}
}
find_lefts();
find_ups();
int vis1[n][m];
int vis2[n][m];
memset(vis1, -1, sizeof(vis1));
memset(vis2, -1, sizeof(vis2));
int ANS = 0;
int VIS = 0;
fr(i, 2, n){
fr(j, 2, m){
++VIS;
for(int k = i - 1; k > 0; k --){
for(auto u : le[k][j]){
if(k == i - 1 || vis1[k][u] == VIS){
vis1[k - 1][u] = VIS;
}
}
}
for(int k = j - 1; k > 0; k --){
for(auto u : up[i][k]){
if(k == j - 1 || vis2[u][k] == VIS){
vis2[u][k - 1] = VIS;
if(vis1[u][k - 1] == VIS) ANS ++;
}
}
}
}
}
// cout << ANS<<endl;
return ANS;
}
/*
int main()
{
freopen("in.txt", "r", stdin);
vector<vector<int> > v;
count_rectangles(v);
return 0;
}
*/
/*
6 5
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
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
168 ms |
293880 KB |
Output is correct |
2 |
Correct |
170 ms |
294020 KB |
Output is correct |
3 |
Correct |
163 ms |
294008 KB |
Output is correct |
4 |
Correct |
164 ms |
294008 KB |
Output is correct |
5 |
Correct |
170 ms |
294008 KB |
Output is correct |
6 |
Correct |
164 ms |
294008 KB |
Output is correct |
7 |
Correct |
165 ms |
294008 KB |
Output is correct |
8 |
Correct |
166 ms |
293884 KB |
Output is correct |
9 |
Correct |
173 ms |
294008 KB |
Output is correct |
10 |
Correct |
166 ms |
294008 KB |
Output is correct |
11 |
Correct |
162 ms |
294008 KB |
Output is correct |
12 |
Correct |
164 ms |
294008 KB |
Output is correct |
13 |
Correct |
162 ms |
293880 KB |
Output is correct |
14 |
Correct |
162 ms |
293880 KB |
Output is correct |
15 |
Correct |
163 ms |
293880 KB |
Output is correct |
16 |
Correct |
161 ms |
293880 KB |
Output is correct |
17 |
Correct |
160 ms |
293880 KB |
Output is correct |
18 |
Correct |
161 ms |
293880 KB |
Output is correct |
19 |
Correct |
169 ms |
294136 KB |
Output is correct |
20 |
Correct |
162 ms |
294008 KB |
Output is correct |
21 |
Correct |
164 ms |
293880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
168 ms |
293880 KB |
Output is correct |
2 |
Correct |
170 ms |
294020 KB |
Output is correct |
3 |
Correct |
163 ms |
294008 KB |
Output is correct |
4 |
Correct |
164 ms |
294008 KB |
Output is correct |
5 |
Correct |
170 ms |
294008 KB |
Output is correct |
6 |
Correct |
164 ms |
294008 KB |
Output is correct |
7 |
Correct |
165 ms |
294008 KB |
Output is correct |
8 |
Correct |
166 ms |
293884 KB |
Output is correct |
9 |
Correct |
173 ms |
294008 KB |
Output is correct |
10 |
Correct |
166 ms |
294008 KB |
Output is correct |
11 |
Correct |
162 ms |
294008 KB |
Output is correct |
12 |
Correct |
164 ms |
294008 KB |
Output is correct |
13 |
Correct |
162 ms |
293880 KB |
Output is correct |
14 |
Correct |
162 ms |
293880 KB |
Output is correct |
15 |
Correct |
163 ms |
293880 KB |
Output is correct |
16 |
Correct |
161 ms |
293880 KB |
Output is correct |
17 |
Correct |
175 ms |
294624 KB |
Output is correct |
18 |
Correct |
184 ms |
294520 KB |
Output is correct |
19 |
Correct |
167 ms |
294392 KB |
Output is correct |
20 |
Correct |
168 ms |
294392 KB |
Output is correct |
21 |
Correct |
179 ms |
294648 KB |
Output is correct |
22 |
Correct |
175 ms |
294520 KB |
Output is correct |
23 |
Correct |
170 ms |
294520 KB |
Output is correct |
24 |
Correct |
166 ms |
294520 KB |
Output is correct |
25 |
Correct |
160 ms |
293880 KB |
Output is correct |
26 |
Correct |
161 ms |
293880 KB |
Output is correct |
27 |
Correct |
169 ms |
294136 KB |
Output is correct |
28 |
Correct |
162 ms |
294008 KB |
Output is correct |
29 |
Correct |
164 ms |
293880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
168 ms |
293880 KB |
Output is correct |
2 |
Correct |
170 ms |
294020 KB |
Output is correct |
3 |
Correct |
163 ms |
294008 KB |
Output is correct |
4 |
Correct |
164 ms |
294008 KB |
Output is correct |
5 |
Correct |
170 ms |
294008 KB |
Output is correct |
6 |
Correct |
164 ms |
294008 KB |
Output is correct |
7 |
Correct |
165 ms |
294008 KB |
Output is correct |
8 |
Correct |
166 ms |
293884 KB |
Output is correct |
9 |
Correct |
173 ms |
294008 KB |
Output is correct |
10 |
Correct |
166 ms |
294008 KB |
Output is correct |
11 |
Correct |
162 ms |
294008 KB |
Output is correct |
12 |
Correct |
164 ms |
294008 KB |
Output is correct |
13 |
Correct |
162 ms |
293880 KB |
Output is correct |
14 |
Correct |
162 ms |
293880 KB |
Output is correct |
15 |
Correct |
163 ms |
293880 KB |
Output is correct |
16 |
Correct |
161 ms |
293880 KB |
Output is correct |
17 |
Correct |
175 ms |
294624 KB |
Output is correct |
18 |
Correct |
184 ms |
294520 KB |
Output is correct |
19 |
Correct |
167 ms |
294392 KB |
Output is correct |
20 |
Correct |
168 ms |
294392 KB |
Output is correct |
21 |
Correct |
179 ms |
294648 KB |
Output is correct |
22 |
Correct |
175 ms |
294520 KB |
Output is correct |
23 |
Correct |
170 ms |
294520 KB |
Output is correct |
24 |
Correct |
166 ms |
294520 KB |
Output is correct |
25 |
Correct |
242 ms |
296056 KB |
Output is correct |
26 |
Correct |
274 ms |
296056 KB |
Output is correct |
27 |
Correct |
252 ms |
296312 KB |
Output is correct |
28 |
Correct |
238 ms |
296312 KB |
Output is correct |
29 |
Correct |
266 ms |
296828 KB |
Output is correct |
30 |
Correct |
266 ms |
297336 KB |
Output is correct |
31 |
Correct |
259 ms |
296952 KB |
Output is correct |
32 |
Correct |
260 ms |
297080 KB |
Output is correct |
33 |
Correct |
160 ms |
293880 KB |
Output is correct |
34 |
Correct |
161 ms |
293880 KB |
Output is correct |
35 |
Correct |
169 ms |
294136 KB |
Output is correct |
36 |
Correct |
162 ms |
294008 KB |
Output is correct |
37 |
Correct |
164 ms |
293880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
168 ms |
293880 KB |
Output is correct |
2 |
Correct |
170 ms |
294020 KB |
Output is correct |
3 |
Correct |
163 ms |
294008 KB |
Output is correct |
4 |
Correct |
164 ms |
294008 KB |
Output is correct |
5 |
Correct |
170 ms |
294008 KB |
Output is correct |
6 |
Correct |
164 ms |
294008 KB |
Output is correct |
7 |
Correct |
165 ms |
294008 KB |
Output is correct |
8 |
Correct |
166 ms |
293884 KB |
Output is correct |
9 |
Correct |
173 ms |
294008 KB |
Output is correct |
10 |
Correct |
166 ms |
294008 KB |
Output is correct |
11 |
Correct |
162 ms |
294008 KB |
Output is correct |
12 |
Correct |
164 ms |
294008 KB |
Output is correct |
13 |
Correct |
162 ms |
293880 KB |
Output is correct |
14 |
Correct |
162 ms |
293880 KB |
Output is correct |
15 |
Correct |
163 ms |
293880 KB |
Output is correct |
16 |
Correct |
161 ms |
293880 KB |
Output is correct |
17 |
Correct |
175 ms |
294624 KB |
Output is correct |
18 |
Correct |
184 ms |
294520 KB |
Output is correct |
19 |
Correct |
167 ms |
294392 KB |
Output is correct |
20 |
Correct |
168 ms |
294392 KB |
Output is correct |
21 |
Correct |
179 ms |
294648 KB |
Output is correct |
22 |
Correct |
175 ms |
294520 KB |
Output is correct |
23 |
Correct |
170 ms |
294520 KB |
Output is correct |
24 |
Correct |
166 ms |
294520 KB |
Output is correct |
25 |
Correct |
242 ms |
296056 KB |
Output is correct |
26 |
Correct |
274 ms |
296056 KB |
Output is correct |
27 |
Correct |
252 ms |
296312 KB |
Output is correct |
28 |
Correct |
238 ms |
296312 KB |
Output is correct |
29 |
Correct |
266 ms |
296828 KB |
Output is correct |
30 |
Correct |
266 ms |
297336 KB |
Output is correct |
31 |
Correct |
259 ms |
296952 KB |
Output is correct |
32 |
Correct |
260 ms |
297080 KB |
Output is correct |
33 |
Correct |
2349 ms |
312500 KB |
Output is correct |
34 |
Correct |
4103 ms |
318712 KB |
Output is correct |
35 |
Correct |
2624 ms |
318756 KB |
Output is correct |
36 |
Execution timed out |
5063 ms |
324772 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
221 ms |
294136 KB |
Output is correct |
2 |
Correct |
207 ms |
294136 KB |
Output is correct |
3 |
Correct |
215 ms |
294008 KB |
Output is correct |
4 |
Correct |
166 ms |
293880 KB |
Output is correct |
5 |
Correct |
213 ms |
294264 KB |
Output is correct |
6 |
Correct |
217 ms |
294396 KB |
Output is correct |
7 |
Correct |
209 ms |
294136 KB |
Output is correct |
8 |
Correct |
215 ms |
294140 KB |
Output is correct |
9 |
Correct |
214 ms |
294264 KB |
Output is correct |
10 |
Correct |
180 ms |
293884 KB |
Output is correct |
11 |
Correct |
186 ms |
294008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
171 ms |
293944 KB |
Output is correct |
2 |
Execution timed out |
5090 ms |
343100 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
168 ms |
293880 KB |
Output is correct |
2 |
Correct |
170 ms |
294020 KB |
Output is correct |
3 |
Correct |
163 ms |
294008 KB |
Output is correct |
4 |
Correct |
164 ms |
294008 KB |
Output is correct |
5 |
Correct |
170 ms |
294008 KB |
Output is correct |
6 |
Correct |
164 ms |
294008 KB |
Output is correct |
7 |
Correct |
165 ms |
294008 KB |
Output is correct |
8 |
Correct |
166 ms |
293884 KB |
Output is correct |
9 |
Correct |
173 ms |
294008 KB |
Output is correct |
10 |
Correct |
166 ms |
294008 KB |
Output is correct |
11 |
Correct |
162 ms |
294008 KB |
Output is correct |
12 |
Correct |
164 ms |
294008 KB |
Output is correct |
13 |
Correct |
162 ms |
293880 KB |
Output is correct |
14 |
Correct |
162 ms |
293880 KB |
Output is correct |
15 |
Correct |
163 ms |
293880 KB |
Output is correct |
16 |
Correct |
161 ms |
293880 KB |
Output is correct |
17 |
Correct |
175 ms |
294624 KB |
Output is correct |
18 |
Correct |
184 ms |
294520 KB |
Output is correct |
19 |
Correct |
167 ms |
294392 KB |
Output is correct |
20 |
Correct |
168 ms |
294392 KB |
Output is correct |
21 |
Correct |
179 ms |
294648 KB |
Output is correct |
22 |
Correct |
175 ms |
294520 KB |
Output is correct |
23 |
Correct |
170 ms |
294520 KB |
Output is correct |
24 |
Correct |
166 ms |
294520 KB |
Output is correct |
25 |
Correct |
242 ms |
296056 KB |
Output is correct |
26 |
Correct |
274 ms |
296056 KB |
Output is correct |
27 |
Correct |
252 ms |
296312 KB |
Output is correct |
28 |
Correct |
238 ms |
296312 KB |
Output is correct |
29 |
Correct |
266 ms |
296828 KB |
Output is correct |
30 |
Correct |
266 ms |
297336 KB |
Output is correct |
31 |
Correct |
259 ms |
296952 KB |
Output is correct |
32 |
Correct |
260 ms |
297080 KB |
Output is correct |
33 |
Correct |
2349 ms |
312500 KB |
Output is correct |
34 |
Correct |
4103 ms |
318712 KB |
Output is correct |
35 |
Correct |
2624 ms |
318756 KB |
Output is correct |
36 |
Execution timed out |
5063 ms |
324772 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |