# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
213455 |
2020-03-25T21:01:00 Z |
Blagojce |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
342780 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();
bool cnt[n][m];
bool cnt2[n][m];
int ANS = 0;
fr(i, 2, n){
fr(j, 2, m){
memset(cnt, false, sizeof(cnt));
memset(cnt2, false, sizeof(cnt2));
for(int k = i - 1; k > 0; k --){
for(auto u : le[k][j]){
if(k == i - 1 || cnt[k][u]){
cnt[k - 1][u] = true;
}
}
}
for(int k = j - 1; k > 0; k --){
for(auto u : up[i][k]){
if(k == j - 1 || cnt2[u][k]){
cnt2[u][k - 1] = true;
if(cnt[u][k - 1]) 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 |
158 ms |
293880 KB |
Output is correct |
2 |
Correct |
167 ms |
294008 KB |
Output is correct |
3 |
Correct |
153 ms |
294008 KB |
Output is correct |
4 |
Correct |
171 ms |
294008 KB |
Output is correct |
5 |
Correct |
153 ms |
294008 KB |
Output is correct |
6 |
Correct |
153 ms |
294008 KB |
Output is correct |
7 |
Correct |
169 ms |
294008 KB |
Output is correct |
8 |
Correct |
158 ms |
293880 KB |
Output is correct |
9 |
Correct |
158 ms |
294008 KB |
Output is correct |
10 |
Correct |
151 ms |
294012 KB |
Output is correct |
11 |
Correct |
173 ms |
294008 KB |
Output is correct |
12 |
Correct |
170 ms |
294008 KB |
Output is correct |
13 |
Correct |
154 ms |
293880 KB |
Output is correct |
14 |
Correct |
150 ms |
293880 KB |
Output is correct |
15 |
Correct |
154 ms |
293880 KB |
Output is correct |
16 |
Correct |
167 ms |
293880 KB |
Output is correct |
17 |
Correct |
155 ms |
293892 KB |
Output is correct |
18 |
Correct |
150 ms |
293880 KB |
Output is correct |
19 |
Correct |
153 ms |
294008 KB |
Output is correct |
20 |
Correct |
166 ms |
294008 KB |
Output is correct |
21 |
Correct |
154 ms |
293880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
158 ms |
293880 KB |
Output is correct |
2 |
Correct |
167 ms |
294008 KB |
Output is correct |
3 |
Correct |
153 ms |
294008 KB |
Output is correct |
4 |
Correct |
171 ms |
294008 KB |
Output is correct |
5 |
Correct |
153 ms |
294008 KB |
Output is correct |
6 |
Correct |
153 ms |
294008 KB |
Output is correct |
7 |
Correct |
169 ms |
294008 KB |
Output is correct |
8 |
Correct |
158 ms |
293880 KB |
Output is correct |
9 |
Correct |
158 ms |
294008 KB |
Output is correct |
10 |
Correct |
151 ms |
294012 KB |
Output is correct |
11 |
Correct |
173 ms |
294008 KB |
Output is correct |
12 |
Correct |
170 ms |
294008 KB |
Output is correct |
13 |
Correct |
154 ms |
293880 KB |
Output is correct |
14 |
Correct |
150 ms |
293880 KB |
Output is correct |
15 |
Correct |
154 ms |
293880 KB |
Output is correct |
16 |
Correct |
167 ms |
293880 KB |
Output is correct |
17 |
Correct |
160 ms |
294392 KB |
Output is correct |
18 |
Correct |
176 ms |
294392 KB |
Output is correct |
19 |
Correct |
158 ms |
294392 KB |
Output is correct |
20 |
Correct |
174 ms |
294392 KB |
Output is correct |
21 |
Correct |
176 ms |
294520 KB |
Output is correct |
22 |
Correct |
164 ms |
294524 KB |
Output is correct |
23 |
Correct |
160 ms |
294520 KB |
Output is correct |
24 |
Correct |
155 ms |
294396 KB |
Output is correct |
25 |
Correct |
155 ms |
293892 KB |
Output is correct |
26 |
Correct |
150 ms |
293880 KB |
Output is correct |
27 |
Correct |
153 ms |
294008 KB |
Output is correct |
28 |
Correct |
166 ms |
294008 KB |
Output is correct |
29 |
Correct |
154 ms |
293880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
158 ms |
293880 KB |
Output is correct |
2 |
Correct |
167 ms |
294008 KB |
Output is correct |
3 |
Correct |
153 ms |
294008 KB |
Output is correct |
4 |
Correct |
171 ms |
294008 KB |
Output is correct |
5 |
Correct |
153 ms |
294008 KB |
Output is correct |
6 |
Correct |
153 ms |
294008 KB |
Output is correct |
7 |
Correct |
169 ms |
294008 KB |
Output is correct |
8 |
Correct |
158 ms |
293880 KB |
Output is correct |
9 |
Correct |
158 ms |
294008 KB |
Output is correct |
10 |
Correct |
151 ms |
294012 KB |
Output is correct |
11 |
Correct |
173 ms |
294008 KB |
Output is correct |
12 |
Correct |
170 ms |
294008 KB |
Output is correct |
13 |
Correct |
154 ms |
293880 KB |
Output is correct |
14 |
Correct |
150 ms |
293880 KB |
Output is correct |
15 |
Correct |
154 ms |
293880 KB |
Output is correct |
16 |
Correct |
167 ms |
293880 KB |
Output is correct |
17 |
Correct |
160 ms |
294392 KB |
Output is correct |
18 |
Correct |
176 ms |
294392 KB |
Output is correct |
19 |
Correct |
158 ms |
294392 KB |
Output is correct |
20 |
Correct |
174 ms |
294392 KB |
Output is correct |
21 |
Correct |
176 ms |
294520 KB |
Output is correct |
22 |
Correct |
164 ms |
294524 KB |
Output is correct |
23 |
Correct |
160 ms |
294520 KB |
Output is correct |
24 |
Correct |
155 ms |
294396 KB |
Output is correct |
25 |
Correct |
321 ms |
295928 KB |
Output is correct |
26 |
Correct |
333 ms |
295928 KB |
Output is correct |
27 |
Correct |
311 ms |
295928 KB |
Output is correct |
28 |
Correct |
318 ms |
295928 KB |
Output is correct |
29 |
Correct |
344 ms |
296696 KB |
Output is correct |
30 |
Correct |
350 ms |
296824 KB |
Output is correct |
31 |
Correct |
340 ms |
296696 KB |
Output is correct |
32 |
Correct |
328 ms |
296696 KB |
Output is correct |
33 |
Correct |
155 ms |
293892 KB |
Output is correct |
34 |
Correct |
150 ms |
293880 KB |
Output is correct |
35 |
Correct |
153 ms |
294008 KB |
Output is correct |
36 |
Correct |
166 ms |
294008 KB |
Output is correct |
37 |
Correct |
154 ms |
293880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
158 ms |
293880 KB |
Output is correct |
2 |
Correct |
167 ms |
294008 KB |
Output is correct |
3 |
Correct |
153 ms |
294008 KB |
Output is correct |
4 |
Correct |
171 ms |
294008 KB |
Output is correct |
5 |
Correct |
153 ms |
294008 KB |
Output is correct |
6 |
Correct |
153 ms |
294008 KB |
Output is correct |
7 |
Correct |
169 ms |
294008 KB |
Output is correct |
8 |
Correct |
158 ms |
293880 KB |
Output is correct |
9 |
Correct |
158 ms |
294008 KB |
Output is correct |
10 |
Correct |
151 ms |
294012 KB |
Output is correct |
11 |
Correct |
173 ms |
294008 KB |
Output is correct |
12 |
Correct |
170 ms |
294008 KB |
Output is correct |
13 |
Correct |
154 ms |
293880 KB |
Output is correct |
14 |
Correct |
150 ms |
293880 KB |
Output is correct |
15 |
Correct |
154 ms |
293880 KB |
Output is correct |
16 |
Correct |
167 ms |
293880 KB |
Output is correct |
17 |
Correct |
160 ms |
294392 KB |
Output is correct |
18 |
Correct |
176 ms |
294392 KB |
Output is correct |
19 |
Correct |
158 ms |
294392 KB |
Output is correct |
20 |
Correct |
174 ms |
294392 KB |
Output is correct |
21 |
Correct |
176 ms |
294520 KB |
Output is correct |
22 |
Correct |
164 ms |
294524 KB |
Output is correct |
23 |
Correct |
160 ms |
294520 KB |
Output is correct |
24 |
Correct |
155 ms |
294396 KB |
Output is correct |
25 |
Correct |
321 ms |
295928 KB |
Output is correct |
26 |
Correct |
333 ms |
295928 KB |
Output is correct |
27 |
Correct |
311 ms |
295928 KB |
Output is correct |
28 |
Correct |
318 ms |
295928 KB |
Output is correct |
29 |
Correct |
344 ms |
296696 KB |
Output is correct |
30 |
Correct |
350 ms |
296824 KB |
Output is correct |
31 |
Correct |
340 ms |
296696 KB |
Output is correct |
32 |
Correct |
328 ms |
296696 KB |
Output is correct |
33 |
Execution timed out |
5108 ms |
309496 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
210 ms |
294136 KB |
Output is correct |
2 |
Correct |
208 ms |
294008 KB |
Output is correct |
3 |
Correct |
192 ms |
294008 KB |
Output is correct |
4 |
Correct |
151 ms |
293880 KB |
Output is correct |
5 |
Correct |
200 ms |
294136 KB |
Output is correct |
6 |
Correct |
197 ms |
294140 KB |
Output is correct |
7 |
Correct |
205 ms |
294136 KB |
Output is correct |
8 |
Correct |
213 ms |
294136 KB |
Output is correct |
9 |
Correct |
199 ms |
294136 KB |
Output is correct |
10 |
Correct |
169 ms |
294008 KB |
Output is correct |
11 |
Correct |
179 ms |
294008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
149 ms |
293880 KB |
Output is correct |
2 |
Execution timed out |
5114 ms |
342780 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
158 ms |
293880 KB |
Output is correct |
2 |
Correct |
167 ms |
294008 KB |
Output is correct |
3 |
Correct |
153 ms |
294008 KB |
Output is correct |
4 |
Correct |
171 ms |
294008 KB |
Output is correct |
5 |
Correct |
153 ms |
294008 KB |
Output is correct |
6 |
Correct |
153 ms |
294008 KB |
Output is correct |
7 |
Correct |
169 ms |
294008 KB |
Output is correct |
8 |
Correct |
158 ms |
293880 KB |
Output is correct |
9 |
Correct |
158 ms |
294008 KB |
Output is correct |
10 |
Correct |
151 ms |
294012 KB |
Output is correct |
11 |
Correct |
173 ms |
294008 KB |
Output is correct |
12 |
Correct |
170 ms |
294008 KB |
Output is correct |
13 |
Correct |
154 ms |
293880 KB |
Output is correct |
14 |
Correct |
150 ms |
293880 KB |
Output is correct |
15 |
Correct |
154 ms |
293880 KB |
Output is correct |
16 |
Correct |
167 ms |
293880 KB |
Output is correct |
17 |
Correct |
160 ms |
294392 KB |
Output is correct |
18 |
Correct |
176 ms |
294392 KB |
Output is correct |
19 |
Correct |
158 ms |
294392 KB |
Output is correct |
20 |
Correct |
174 ms |
294392 KB |
Output is correct |
21 |
Correct |
176 ms |
294520 KB |
Output is correct |
22 |
Correct |
164 ms |
294524 KB |
Output is correct |
23 |
Correct |
160 ms |
294520 KB |
Output is correct |
24 |
Correct |
155 ms |
294396 KB |
Output is correct |
25 |
Correct |
321 ms |
295928 KB |
Output is correct |
26 |
Correct |
333 ms |
295928 KB |
Output is correct |
27 |
Correct |
311 ms |
295928 KB |
Output is correct |
28 |
Correct |
318 ms |
295928 KB |
Output is correct |
29 |
Correct |
344 ms |
296696 KB |
Output is correct |
30 |
Correct |
350 ms |
296824 KB |
Output is correct |
31 |
Correct |
340 ms |
296696 KB |
Output is correct |
32 |
Correct |
328 ms |
296696 KB |
Output is correct |
33 |
Execution timed out |
5108 ms |
309496 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |