oj.uz

Submission #535418

# Submission time Handle Problem Language Result Execution time Memory
535418 2022-03-10T09:07:34 Z mario05092929 Rectangles (IOI19_rect) C++14
100 / 100
 3366 ms 718452 KB 
#include "rect.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e16;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,m,a[2505][2505];
int L[2505][2505],R[2505][2505],U[2505][2505],D[2505][2505];
stack <pi> s;
vec N[2505][2505],M[2505][2505];
vector <pair<pi,pi>> V;

void make_LRUD() {
	for(int i = 1;i <= n;i++) {
		s.push({INF,-1});
		for(int j = 1;j <= m;j++) {
			while(s.top().x <= a[i][j]) s.pop();
			L[i][j] = s.top().y;
			s.push({a[i][j],j});
		}
		while(!s.empty()) s.pop();
	}
	for(int i = 1;i <= n;i++) {
		s.push({INF,-1});
		for(int j = m;j >= 1;j--) {
			while(s.top().x <= a[i][j]) s.pop();
			R[i][j] = s.top().y;
			s.push({a[i][j],j});
		}
		while(!s.empty()) s.pop();
	}
	for(int i = 1;i <= m;i++) {
		s.push({INF,-1});
		for(int j = 1;j <= n;j++) {
			while(s.top().x <= a[j][i]) s.pop();
			U[j][i] = s.top().y;
			s.push({a[j][i],j});
		}
		while(!s.empty()) s.pop();
	}
	for(int i = 1;i <= m;i++) {
		s.push({INF,-1});
		for(int j = n;j >= 1;j--) {
			while(s.top().x <= a[j][i]) s.pop();
			D[j][i] = s.top().y;
			s.push({a[j][i],j});
		}
		while(!s.empty()) s.pop();
	}
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            int sx = U[i][j], sy = L[i][j], ex = D[i][j], ey = R[i][j];
            if(sx != -1&&ex != -1) N[sx][ex].pb(j);
            if(sy != -1&&ey != -1) M[sy][ey].pb(i);
        }
    }
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) sort(all(N[i][j])), N[i][j].erase(unique(all(N[i][j])),N[i][j].end());
    }
    for(int i = 1;i <= m;i++) {
        for(int j = 1;j <= m;j++) sort(all(M[i][j])), M[i][j].erase(unique(all(M[i][j])),M[i][j].end());
    }
}

ll count_rectangles(vector<vector<int>> A) {
    n = A.size(), m = A[0].size();
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) a[i+1][j+1] = A[i][j];
    }
    make_LRUD();
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            int sx = U[i][j], sy = L[i][j], ex = D[i][j], ey = R[i][j];
            if(sx == -1||sy == -1||ex == -1||ey == -1) continue;
            int L = upper_bound(all(N[sx][ex]),sy)-N[sx][ex].begin();
            int R = lower_bound(all(N[sx][ex]),ey)-N[sx][ex].begin()-1;
            if(L == N[sx][ex].size()||R == -1||R-L != ey-sy-2) continue;
            L = upper_bound(all(M[sy][ey]),sx)-M[sy][ey].begin();
            R = lower_bound(all(M[sy][ey]),ex)-M[sy][ey].begin()-1;
            if(L == M[sy][ey].size()||R == -1||R-L != ex-sx-2) continue;
            V.pb({{sx,sy},{ex,ey}});
        }
    }
    sort(all(V)), V.erase(unique(all(V)),V.end());
    return V.size();
}

Compilation message

rect.cpp:7: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    7 | #pragma gcc optimize("O3")
      | 
rect.cpp:8: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    8 | #pragma gcc optimize("Ofast")
      | 
rect.cpp:9: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    9 | #pragma gcc optimize("unroll-loops")
      | 
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             if(L == N[sx][ex].size()||R == -1||R-L != ey-sy-2) continue;
      |                ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             if(L == M[sy][ey].size()||R == -1||R-L != ex-sx-2) continue;
      |                ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 295064 KB Output is correct
2 Correct 160 ms 295692 KB Output is correct
3 Correct 167 ms 295652 KB Output is correct
4 Correct 172 ms 295628 KB Output is correct
5 Correct 171 ms 295588 KB Output is correct
6 Correct 151 ms 295640 KB Output is correct
7 Correct 155 ms 295532 KB Output is correct
8 Correct 171 ms 295164 KB Output is correct
9 Correct 147 ms 295628 KB Output is correct
10 Correct 155 ms 295616 KB Output is correct
11 Correct 158 ms 295576 KB Output is correct
12 Correct 152 ms 295584 KB Output is correct
13 Correct 144 ms 294932 KB Output is correct
14 Correct 158 ms 295132 KB Output is correct
15 Correct 178 ms 295216 KB Output is correct
16 Correct 167 ms 294968 KB Output is correct
17 Correct 173 ms 295048 KB Output is correct
18 Correct 172 ms 294940 KB Output is correct
19 Correct 156 ms 295620 KB Output is correct
20 Correct 161 ms 295556 KB Output is correct
21 Correct 152 ms 295156 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 295064 KB Output is correct
2 Correct 160 ms 295692 KB Output is correct
3 Correct 167 ms 295652 KB Output is correct
4 Correct 172 ms 295628 KB Output is correct
5 Correct 171 ms 295588 KB Output is correct
6 Correct 151 ms 295640 KB Output is correct
7 Correct 155 ms 295532 KB Output is correct
8 Correct 171 ms 295164 KB Output is correct
9 Correct 147 ms 295628 KB Output is correct
10 Correct 155 ms 295616 KB Output is correct
11 Correct 158 ms 295576 KB Output is correct
12 Correct 152 ms 295584 KB Output is correct
13 Correct 144 ms 294932 KB Output is correct
14 Correct 158 ms 295132 KB Output is correct
15 Correct 178 ms 295216 KB Output is correct
16 Correct 167 ms 294968 KB Output is correct
17 Correct 173 ms 295048 KB Output is correct
18 Correct 172 ms 294940 KB Output is correct
19 Correct 156 ms 295620 KB Output is correct
20 Correct 161 ms 295556 KB Output is correct
21 Correct 152 ms 295156 KB Output is correct
22 Correct 170 ms 297060 KB Output is correct
23 Correct 167 ms 297084 KB Output is correct
24 Correct 161 ms 297120 KB Output is correct
25 Correct 160 ms 296784 KB Output is correct
26 Correct 152 ms 296932 KB Output is correct
27 Correct 174 ms 296928 KB Output is correct
28 Correct 166 ms 297024 KB Output is correct
29 Correct 156 ms 296728 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 295064 KB Output is correct
2 Correct 160 ms 295692 KB Output is correct
3 Correct 167 ms 295652 KB Output is correct
4 Correct 172 ms 295628 KB Output is correct
5 Correct 171 ms 295588 KB Output is correct
6 Correct 151 ms 295640 KB Output is correct
7 Correct 155 ms 295532 KB Output is correct
8 Correct 171 ms 295164 KB Output is correct
9 Correct 147 ms 295628 KB Output is correct
10 Correct 155 ms 295616 KB Output is correct
11 Correct 158 ms 295576 KB Output is correct
12 Correct 152 ms 295584 KB Output is correct
13 Correct 144 ms 294932 KB Output is correct
14 Correct 158 ms 295132 KB Output is correct
15 Correct 178 ms 295216 KB Output is correct
16 Correct 167 ms 294968 KB Output is correct
17 Correct 170 ms 297060 KB Output is correct
18 Correct 167 ms 297084 KB Output is correct
19 Correct 161 ms 297120 KB Output is correct
20 Correct 160 ms 296784 KB Output is correct
21 Correct 152 ms 296932 KB Output is correct
22 Correct 174 ms 296928 KB Output is correct
23 Correct 166 ms 297024 KB Output is correct
24 Correct 156 ms 296728 KB Output is correct
25 Correct 173 ms 295048 KB Output is correct
26 Correct 172 ms 294940 KB Output is correct
27 Correct 156 ms 295620 KB Output is correct
28 Correct 161 ms 295556 KB Output is correct
29 Correct 152 ms 295156 KB Output is correct
30 Correct 178 ms 301904 KB Output is correct
31 Correct 173 ms 301888 KB Output is correct
32 Correct 169 ms 301908 KB Output is correct
33 Correct 182 ms 300684 KB Output is correct
34 Correct 189 ms 301284 KB Output is correct
35 Correct 193 ms 301372 KB Output is correct
36 Correct 189 ms 301492 KB Output is correct
37 Correct 181 ms 301324 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 295064 KB Output is correct
2 Correct 160 ms 295692 KB Output is correct
3 Correct 167 ms 295652 KB Output is correct
4 Correct 172 ms 295628 KB Output is correct
5 Correct 171 ms 295588 KB Output is correct
6 Correct 151 ms 295640 KB Output is correct
7 Correct 155 ms 295532 KB Output is correct
8 Correct 171 ms 295164 KB Output is correct
9 Correct 147 ms 295628 KB Output is correct
10 Correct 155 ms 295616 KB Output is correct
11 Correct 158 ms 295576 KB Output is correct
12 Correct 152 ms 295584 KB Output is correct
13 Correct 144 ms 294932 KB Output is correct
14 Correct 158 ms 295132 KB Output is correct
15 Correct 178 ms 295216 KB Output is correct
16 Correct 167 ms 294968 KB Output is correct
17 Correct 170 ms 297060 KB Output is correct
18 Correct 167 ms 297084 KB Output is correct
19 Correct 161 ms 297120 KB Output is correct
20 Correct 160 ms 296784 KB Output is correct
21 Correct 152 ms 296932 KB Output is correct
22 Correct 174 ms 296928 KB Output is correct
23 Correct 166 ms 297024 KB Output is correct
24 Correct 156 ms 296728 KB Output is correct
25 Correct 178 ms 301904 KB Output is correct
26 Correct 173 ms 301888 KB Output is correct
27 Correct 169 ms 301908 KB Output is correct
28 Correct 182 ms 300684 KB Output is correct
29 Correct 189 ms 301284 KB Output is correct
30 Correct 193 ms 301372 KB Output is correct
31 Correct 189 ms 301492 KB Output is correct
32 Correct 181 ms 301324 KB Output is correct
33 Correct 173 ms 295048 KB Output is correct
34 Correct 172 ms 294940 KB Output is correct
35 Correct 156 ms 295620 KB Output is correct
36 Correct 161 ms 295556 KB Output is correct
37 Correct 152 ms 295156 KB Output is correct
38 Correct 276 ms 340864 KB Output is correct
39 Correct 272 ms 340944 KB Output is correct
40 Correct 293 ms 340932 KB Output is correct
41 Correct 298 ms 340864 KB Output is correct
42 Correct 347 ms 339748 KB Output is correct
43 Correct 367 ms 339760 KB Output is correct
44 Correct 362 ms 340120 KB Output is correct
45 Correct 385 ms 338048 KB Output is correct
46 Correct 292 ms 327096 KB Output is correct
47 Correct 324 ms 328464 KB Output is correct
48 Correct 405 ms 334888 KB Output is correct
49 Correct 419 ms 336952 KB Output is correct
50 Correct 319 ms 323176 KB Output is correct
51 Correct 287 ms 316148 KB Output is correct
52 Correct 384 ms 335200 KB Output is correct
53 Correct 419 ms 336148 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 295500 KB Output is correct
2 Correct 183 ms 295396 KB Output is correct
3 Correct 221 ms 295256 KB Output is correct
4 Correct 180 ms 295040 KB Output is correct
5 Correct 189 ms 295460 KB Output is correct
6 Correct 198 ms 295496 KB Output is correct
7 Correct 187 ms 295512 KB Output is correct
8 Correct 202 ms 295380 KB Output is correct
9 Correct 193 ms 295436 KB Output is correct
10 Correct 167 ms 295192 KB Output is correct
11 Correct 182 ms 295244 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 295048 KB Output is correct
2 Correct 172 ms 294940 KB Output is correct
3 Correct 156 ms 295620 KB Output is correct
4 Correct 161 ms 295556 KB Output is correct
5 Correct 152 ms 295156 KB Output is correct
6 Correct 142 ms 295172 KB Output is correct
7 Correct 728 ms 406780 KB Output is correct
8 Correct 1467 ms 524928 KB Output is correct
9 Correct 1417 ms 526040 KB Output is correct
10 Correct 1469 ms 525928 KB Output is correct
11 Correct 417 ms 385804 KB Output is correct
12 Correct 647 ms 475064 KB Output is correct
13 Correct 747 ms 478832 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 295064 KB Output is correct
2 Correct 160 ms 295692 KB Output is correct
3 Correct 167 ms 295652 KB Output is correct
4 Correct 172 ms 295628 KB Output is correct
5 Correct 171 ms 295588 KB Output is correct
6 Correct 151 ms 295640 KB Output is correct
7 Correct 155 ms 295532 KB Output is correct
8 Correct 171 ms 295164 KB Output is correct
9 Correct 147 ms 295628 KB Output is correct
10 Correct 155 ms 295616 KB Output is correct
11 Correct 158 ms 295576 KB Output is correct
12 Correct 152 ms 295584 KB Output is correct
13 Correct 144 ms 294932 KB Output is correct
14 Correct 158 ms 295132 KB Output is correct
15 Correct 178 ms 295216 KB Output is correct
16 Correct 167 ms 294968 KB Output is correct
17 Correct 170 ms 297060 KB Output is correct
18 Correct 167 ms 297084 KB Output is correct
19 Correct 161 ms 297120 KB Output is correct
20 Correct 160 ms 296784 KB Output is correct
21 Correct 152 ms 296932 KB Output is correct
22 Correct 174 ms 296928 KB Output is correct
23 Correct 166 ms 297024 KB Output is correct
24 Correct 156 ms 296728 KB Output is correct
25 Correct 178 ms 301904 KB Output is correct
26 Correct 173 ms 301888 KB Output is correct
27 Correct 169 ms 301908 KB Output is correct
28 Correct 182 ms 300684 KB Output is correct
29 Correct 189 ms 301284 KB Output is correct
30 Correct 193 ms 301372 KB Output is correct
31 Correct 189 ms 301492 KB Output is correct
32 Correct 181 ms 301324 KB Output is correct
33 Correct 276 ms 340864 KB Output is correct
34 Correct 272 ms 340944 KB Output is correct
35 Correct 293 ms 340932 KB Output is correct
36 Correct 298 ms 340864 KB Output is correct
37 Correct 347 ms 339748 KB Output is correct
38 Correct 367 ms 339760 KB Output is correct
39 Correct 362 ms 340120 KB Output is correct
40 Correct 385 ms 338048 KB Output is correct
41 Correct 292 ms 327096 KB Output is correct
42 Correct 324 ms 328464 KB Output is correct
43 Correct 405 ms 334888 KB Output is correct
44 Correct 419 ms 336952 KB Output is correct
45 Correct 319 ms 323176 KB Output is correct
46 Correct 287 ms 316148 KB Output is correct
47 Correct 384 ms 335200 KB Output is correct
48 Correct 419 ms 336148 KB Output is correct
49 Correct 213 ms 295500 KB Output is correct
50 Correct 183 ms 295396 KB Output is correct
51 Correct 221 ms 295256 KB Output is correct
52 Correct 180 ms 295040 KB Output is correct
53 Correct 189 ms 295460 KB Output is correct
54 Correct 198 ms 295496 KB Output is correct
55 Correct 187 ms 295512 KB Output is correct
56 Correct 202 ms 295380 KB Output is correct
57 Correct 193 ms 295436 KB Output is correct
58 Correct 167 ms 295192 KB Output is correct
59 Correct 182 ms 295244 KB Output is correct
60 Correct 142 ms 295172 KB Output is correct
61 Correct 728 ms 406780 KB Output is correct
62 Correct 1467 ms 524928 KB Output is correct
63 Correct 1417 ms 526040 KB Output is correct
64 Correct 1469 ms 525928 KB Output is correct
65 Correct 417 ms 385804 KB Output is correct
66 Correct 647 ms 475064 KB Output is correct
67 Correct 747 ms 478832 KB Output is correct
68 Correct 173 ms 295048 KB Output is correct
69 Correct 172 ms 294940 KB Output is correct
70 Correct 156 ms 295620 KB Output is correct
71 Correct 161 ms 295556 KB Output is correct
72 Correct 152 ms 295156 KB Output is correct
73 Correct 1377 ms 709016 KB Output is correct
74 Correct 1129 ms 709136 KB Output is correct
75 Correct 1602 ms 709084 KB Output is correct
76 Correct 1373 ms 708996 KB Output is correct
77 Correct 2450 ms 718432 KB Output is correct
78 Correct 1654 ms 490892 KB Output is correct
79 Correct 1743 ms 556120 KB Output is correct
80 Correct 2766 ms 629664 KB Output is correct
81 Correct 1914 ms 507096 KB Output is correct
82 Correct 2674 ms 592424 KB Output is correct
83 Correct 3268 ms 656516 KB Output is correct
84 Correct 2081 ms 495088 KB Output is correct
85 Correct 3360 ms 652448 KB Output is correct
86 Correct 3366 ms 644512 KB Output is correct
87 Correct 1679 ms 584180 KB Output is correct
88 Correct 2966 ms 718428 KB Output is correct
89 Correct 2852 ms 718284 KB Output is correct
90 Correct 2875 ms 718452 KB Output is correct