oj.uz

Submission #889034

# Submission time Handle Problem Language Result Execution time Memory
889034 2023-12-18T16:14:38 Z abczz Rectangles (IOI19_rect) C++14
100 / 100
 2149 ms 807320 KB 
#include "rect.h"
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#define ll long long
 
using namespace std;

vector <ll> U;
vector <array<ll, 2>> V;
vector <array<ll, 2>> tmp;
vector <array<ll, 2>> A[2500][2500], B[2500][2500];
ll bit[2501], upd[2500][2500], nx[2500][2500], n, m, f, l, r, mid, cnt, z;
 
void add(ll u) {
	while (u <= n) {
		U.push_back(u);
		++bit[u];
		u += u & -u;
	}
}
 
ll query(ll u) {
	ll res = 0;
	while (u) {
		res += bit[u];
		u -= u & -u;
	}
	return res;
}
 
long long count_rectangles(std::vector<std::vector<int> > a) {
	n = a.size(), m = a[0].size(), f = 0;
	for (int i=0; i<n; ++i) {
		V.clear();
		for (int j=0; j<m; ++j) {
			while (!V.empty()) {
        auto [u, id] = V.back();
        if (u <= a[i][j]) V.pop_back();
        else break;
      }
      if (j && j != m-1 && a[i][j] < a[i][j+1]) {
        z = V.size()-1;
        while (z >= 0) {
          A[i][j].push_back({V[z][1]+1, i});
          if (V[z][0] >= a[i][j+1]) break;
          --z;
        }
      }
      if (V.empty() || V.back()[0] > a[i][j]) V.push_back({a[i][j], j});
		}
		for (int j=0; j<m; ++j) {
      reverse(A[i][j].begin(), A[i][j].end());
			if (i && !A[i][j].empty()) {
				int k = 0;
				for (auto [u, v] : A[i-1][j]) {
					while (k < A[i][j].size()-1 && A[i][j][k][0] < u) ++k;
					if (A[i][j][k][0] == u) A[i][j][k][1] = v;
				}
			}
		}
	}
	for (int i=0; i<n; ++i) {
		for (int j=0; j<n; ++j) {
			upd[i][j] = -2;
		}
	}
	for (int j=0; j<m; ++j) {
		V.clear();
		for (int i=0; i<n; ++i) {
			while (!V.empty()) {
        auto [u, id] = V.back();
        if (u <= a[i][j]) V.pop_back();
        else break;
      }
      if (i && i != n-1 && a[i][j] < a[i+1][j]) {
        z = V.size()-1;
        while (z >= 0) {
          upd[V[z][1]+1][i] = j;
          B[i][j].push_back({j, V[z][1]+1});
          if (V[z][0] >= a[i+1][j]) break;
          --z;
        }
      }
      if (V.empty() || V.back()[0] > a[i][j]) V.push_back({a[i][j], i});
		}
		for (int i=0; i<n; ++i) {
			if (j && !B[i][j].empty()) {
				int k = 0;
				tmp.clear();
				for (auto [u, v] : B[i][j-1]) {
					if (upd[v][i] == j) {
						upd[v][i] = -1;
						tmp.push_back({u, v});
					}
				}
				for (auto [u, v] : B[i][j]) {
					if (upd[v][i] == -1) {
						upd[v][i] = j;
					}
					else tmp.push_back({u, v});
				}
				swap(B[i][j], tmp);
			}
		}
	}
	for (int i=0; i<n; ++i) {
		for (int j=0; j<m; ++j) {
			ll l = 0, r = 0;
			while (l < A[i][j].size() && r < B[i][j].size()) {
				if (B[i][j][r][0] <= A[i][j][l][0]) {
					add(n-B[i][j][r][1]);
					++r;
				}
				else {
					f += query(n-A[i][j][l][1]);
					++l;
				}
			}
			while (l < A[i][j].size()) {
				f += query(n-A[i][j][l][1]);
				++l;
			}
			while (!U.empty()) {
				auto u = U.back();
				U.pop_back();
				bit[u] = 0;
			}
		}
	}
	return f;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:39:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |         auto [u, id] = V.back();
      |              ^
rect.cpp:57:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for (auto [u, v] : A[i-1][j]) {
      |               ^
rect.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |      while (k < A[i][j].size()-1 && A[i][j][k][0] < u) ++k;
      |             ~~^~~~~~~~~~~~~~~~~~
rect.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |         auto [u, id] = V.back();
      |              ^
rect.cpp:92:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |     for (auto [u, v] : B[i][j-1]) {
      |               ^
rect.cpp:98:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |     for (auto [u, v] : B[i][j]) {
      |               ^
rect.cpp:90:9: warning: unused variable 'k' [-Wunused-variable]
   90 |     int k = 0;
      |         ^
rect.cpp:111:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |    while (l < A[i][j].size() && r < B[i][j].size()) {
      |           ~~^~~~~~~~~~~~~~~~
rect.cpp:111:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |    while (l < A[i][j].size() && r < B[i][j].size()) {
      |                                 ~~^~~~~~~~~~~~~~~~
rect.cpp:121:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |    while (l < A[i][j].size()) {
      |           ~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 297044 KB Output is correct
2 Correct 64 ms 299264 KB Output is correct
3 Correct 63 ms 299200 KB Output is correct
4 Correct 63 ms 299344 KB Output is correct
5 Correct 71 ms 299128 KB Output is correct
6 Correct 66 ms 299348 KB Output is correct
7 Correct 63 ms 299088 KB Output is correct
8 Correct 83 ms 297044 KB Output is correct
9 Correct 62 ms 299348 KB Output is correct
10 Correct 63 ms 299204 KB Output is correct
11 Correct 64 ms 299324 KB Output is correct
12 Correct 62 ms 299348 KB Output is correct
13 Correct 63 ms 297044 KB Output is correct
14 Correct 63 ms 297044 KB Output is correct
15 Correct 64 ms 297040 KB Output is correct
16 Correct 63 ms 297044 KB Output is correct
17 Correct 68 ms 297232 KB Output is correct
18 Correct 63 ms 297044 KB Output is correct
19 Correct 63 ms 299088 KB Output is correct
20 Correct 63 ms 299092 KB Output is correct
21 Correct 63 ms 297192 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 297044 KB Output is correct
2 Correct 64 ms 299264 KB Output is correct
3 Correct 63 ms 299200 KB Output is correct
4 Correct 63 ms 299344 KB Output is correct
5 Correct 71 ms 299128 KB Output is correct
6 Correct 66 ms 299348 KB Output is correct
7 Correct 63 ms 299088 KB Output is correct
8 Correct 83 ms 297044 KB Output is correct
9 Correct 62 ms 299348 KB Output is correct
10 Correct 63 ms 299204 KB Output is correct
11 Correct 64 ms 299324 KB Output is correct
12 Correct 62 ms 299348 KB Output is correct
13 Correct 63 ms 297044 KB Output is correct
14 Correct 63 ms 297044 KB Output is correct
15 Correct 64 ms 297040 KB Output is correct
16 Correct 63 ms 297044 KB Output is correct
17 Correct 68 ms 297232 KB Output is correct
18 Correct 63 ms 297044 KB Output is correct
19 Correct 63 ms 299088 KB Output is correct
20 Correct 63 ms 299092 KB Output is correct
21 Correct 63 ms 297192 KB Output is correct
22 Correct 65 ms 299600 KB Output is correct
23 Correct 64 ms 299604 KB Output is correct
24 Correct 69 ms 300000 KB Output is correct
25 Correct 65 ms 299396 KB Output is correct
26 Correct 64 ms 299664 KB Output is correct
27 Correct 65 ms 299604 KB Output is correct
28 Correct 64 ms 299704 KB Output is correct
29 Correct 62 ms 299348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 297044 KB Output is correct
2 Correct 64 ms 299264 KB Output is correct
3 Correct 63 ms 299200 KB Output is correct
4 Correct 63 ms 299344 KB Output is correct
5 Correct 71 ms 299128 KB Output is correct
6 Correct 66 ms 299348 KB Output is correct
7 Correct 63 ms 299088 KB Output is correct
8 Correct 83 ms 297044 KB Output is correct
9 Correct 62 ms 299348 KB Output is correct
10 Correct 63 ms 299204 KB Output is correct
11 Correct 64 ms 299324 KB Output is correct
12 Correct 62 ms 299348 KB Output is correct
13 Correct 63 ms 297044 KB Output is correct
14 Correct 63 ms 297044 KB Output is correct
15 Correct 64 ms 297040 KB Output is correct
16 Correct 63 ms 297044 KB Output is correct
17 Correct 65 ms 299600 KB Output is correct
18 Correct 64 ms 299604 KB Output is correct
19 Correct 69 ms 300000 KB Output is correct
20 Correct 65 ms 299396 KB Output is correct
21 Correct 64 ms 299664 KB Output is correct
22 Correct 65 ms 299604 KB Output is correct
23 Correct 64 ms 299704 KB Output is correct
24 Correct 62 ms 299348 KB Output is correct
25 Correct 68 ms 297232 KB Output is correct
26 Correct 63 ms 297044 KB Output is correct
27 Correct 63 ms 299088 KB Output is correct
28 Correct 63 ms 299092 KB Output is correct
29 Correct 63 ms 297192 KB Output is correct
30 Correct 68 ms 303440 KB Output is correct
31 Correct 68 ms 303440 KB Output is correct
32 Correct 68 ms 303444 KB Output is correct
33 Correct 69 ms 302472 KB Output is correct
34 Correct 71 ms 303952 KB Output is correct
35 Correct 72 ms 304212 KB Output is correct
36 Correct 72 ms 303956 KB Output is correct
37 Correct 72 ms 303952 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 297044 KB Output is correct
2 Correct 64 ms 299264 KB Output is correct
3 Correct 63 ms 299200 KB Output is correct
4 Correct 63 ms 299344 KB Output is correct
5 Correct 71 ms 299128 KB Output is correct
6 Correct 66 ms 299348 KB Output is correct
7 Correct 63 ms 299088 KB Output is correct
8 Correct 83 ms 297044 KB Output is correct
9 Correct 62 ms 299348 KB Output is correct
10 Correct 63 ms 299204 KB Output is correct
11 Correct 64 ms 299324 KB Output is correct
12 Correct 62 ms 299348 KB Output is correct
13 Correct 63 ms 297044 KB Output is correct
14 Correct 63 ms 297044 KB Output is correct
15 Correct 64 ms 297040 KB Output is correct
16 Correct 63 ms 297044 KB Output is correct
17 Correct 65 ms 299600 KB Output is correct
18 Correct 64 ms 299604 KB Output is correct
19 Correct 69 ms 300000 KB Output is correct
20 Correct 65 ms 299396 KB Output is correct
21 Correct 64 ms 299664 KB Output is correct
22 Correct 65 ms 299604 KB Output is correct
23 Correct 64 ms 299704 KB Output is correct
24 Correct 62 ms 299348 KB Output is correct
25 Correct 68 ms 303440 KB Output is correct
26 Correct 68 ms 303440 KB Output is correct
27 Correct 68 ms 303444 KB Output is correct
28 Correct 69 ms 302472 KB Output is correct
29 Correct 71 ms 303952 KB Output is correct
30 Correct 72 ms 304212 KB Output is correct
31 Correct 72 ms 303956 KB Output is correct
32 Correct 72 ms 303952 KB Output is correct
33 Correct 68 ms 297232 KB Output is correct
34 Correct 63 ms 297044 KB Output is correct
35 Correct 63 ms 299088 KB Output is correct
36 Correct 63 ms 299092 KB Output is correct
37 Correct 63 ms 297192 KB Output is correct
38 Correct 110 ms 329044 KB Output is correct
39 Correct 114 ms 331344 KB Output is correct
40 Correct 117 ms 331956 KB Output is correct
41 Correct 115 ms 333848 KB Output is correct
42 Correct 118 ms 339792 KB Output is correct
43 Correct 117 ms 339792 KB Output is correct
44 Correct 118 ms 340184 KB Output is correct
45 Correct 116 ms 336424 KB Output is correct
46 Correct 111 ms 323900 KB Output is correct
47 Correct 136 ms 327760 KB Output is correct
48 Correct 185 ms 345020 KB Output is correct
49 Correct 186 ms 347368 KB Output is correct
50 Correct 129 ms 329392 KB Output is correct
51 Correct 134 ms 323124 KB Output is correct
52 Correct 191 ms 344200 KB Output is correct
53 Correct 183 ms 345172 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 297556 KB Output is correct
2 Correct 63 ms 297328 KB Output is correct
3 Correct 63 ms 297296 KB Output is correct
4 Correct 64 ms 297044 KB Output is correct
5 Correct 64 ms 297556 KB Output is correct
6 Correct 63 ms 297352 KB Output is correct
7 Correct 63 ms 297556 KB Output is correct
8 Correct 64 ms 297520 KB Output is correct
9 Correct 70 ms 297552 KB Output is correct
10 Correct 63 ms 297296 KB Output is correct
11 Correct 62 ms 297308 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 297232 KB Output is correct
2 Correct 63 ms 297044 KB Output is correct
3 Correct 63 ms 299088 KB Output is correct
4 Correct 63 ms 299092 KB Output is correct
5 Correct 63 ms 297192 KB Output is correct
6 Correct 63 ms 297040 KB Output is correct
7 Correct 345 ms 394488 KB Output is correct
8 Correct 813 ms 502800 KB Output is correct
9 Correct 794 ms 503400 KB Output is correct
10 Correct 760 ms 503336 KB Output is correct
11 Correct 210 ms 352096 KB Output is correct
12 Correct 307 ms 401960 KB Output is correct
13 Correct 339 ms 405584 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 297044 KB Output is correct
2 Correct 64 ms 299264 KB Output is correct
3 Correct 63 ms 299200 KB Output is correct
4 Correct 63 ms 299344 KB Output is correct
5 Correct 71 ms 299128 KB Output is correct
6 Correct 66 ms 299348 KB Output is correct
7 Correct 63 ms 299088 KB Output is correct
8 Correct 83 ms 297044 KB Output is correct
9 Correct 62 ms 299348 KB Output is correct
10 Correct 63 ms 299204 KB Output is correct
11 Correct 64 ms 299324 KB Output is correct
12 Correct 62 ms 299348 KB Output is correct
13 Correct 63 ms 297044 KB Output is correct
14 Correct 63 ms 297044 KB Output is correct
15 Correct 64 ms 297040 KB Output is correct
16 Correct 63 ms 297044 KB Output is correct
17 Correct 65 ms 299600 KB Output is correct
18 Correct 64 ms 299604 KB Output is correct
19 Correct 69 ms 300000 KB Output is correct
20 Correct 65 ms 299396 KB Output is correct
21 Correct 64 ms 299664 KB Output is correct
22 Correct 65 ms 299604 KB Output is correct
23 Correct 64 ms 299704 KB Output is correct
24 Correct 62 ms 299348 KB Output is correct
25 Correct 68 ms 303440 KB Output is correct
26 Correct 68 ms 303440 KB Output is correct
27 Correct 68 ms 303444 KB Output is correct
28 Correct 69 ms 302472 KB Output is correct
29 Correct 71 ms 303952 KB Output is correct
30 Correct 72 ms 304212 KB Output is correct
31 Correct 72 ms 303956 KB Output is correct
32 Correct 72 ms 303952 KB Output is correct
33 Correct 110 ms 329044 KB Output is correct
34 Correct 114 ms 331344 KB Output is correct
35 Correct 117 ms 331956 KB Output is correct
36 Correct 115 ms 333848 KB Output is correct
37 Correct 118 ms 339792 KB Output is correct
38 Correct 117 ms 339792 KB Output is correct
39 Correct 118 ms 340184 KB Output is correct
40 Correct 116 ms 336424 KB Output is correct
41 Correct 111 ms 323900 KB Output is correct
42 Correct 136 ms 327760 KB Output is correct
43 Correct 185 ms 345020 KB Output is correct
44 Correct 186 ms 347368 KB Output is correct
45 Correct 129 ms 329392 KB Output is correct
46 Correct 134 ms 323124 KB Output is correct
47 Correct 191 ms 344200 KB Output is correct
48 Correct 183 ms 345172 KB Output is correct
49 Correct 64 ms 297556 KB Output is correct
50 Correct 63 ms 297328 KB Output is correct
51 Correct 63 ms 297296 KB Output is correct
52 Correct 64 ms 297044 KB Output is correct
53 Correct 64 ms 297556 KB Output is correct
54 Correct 63 ms 297352 KB Output is correct
55 Correct 63 ms 297556 KB Output is correct
56 Correct 64 ms 297520 KB Output is correct
57 Correct 70 ms 297552 KB Output is correct
58 Correct 63 ms 297296 KB Output is correct
59 Correct 62 ms 297308 KB Output is correct
60 Correct 63 ms 297040 KB Output is correct
61 Correct 345 ms 394488 KB Output is correct
62 Correct 813 ms 502800 KB Output is correct
63 Correct 794 ms 503400 KB Output is correct
64 Correct 760 ms 503336 KB Output is correct
65 Correct 210 ms 352096 KB Output is correct
66 Correct 307 ms 401960 KB Output is correct
67 Correct 339 ms 405584 KB Output is correct
68 Correct 68 ms 297232 KB Output is correct
69 Correct 63 ms 297044 KB Output is correct
70 Correct 63 ms 299088 KB Output is correct
71 Correct 63 ms 299092 KB Output is correct
72 Correct 63 ms 297192 KB Output is correct
73 Correct 713 ms 553556 KB Output is correct
74 Correct 792 ms 591952 KB Output is correct
75 Correct 907 ms 596484 KB Output is correct
76 Correct 1039 ms 635256 KB Output is correct
77 Correct 819 ms 657744 KB Output is correct
78 Correct 1141 ms 586796 KB Output is correct
79 Correct 1384 ms 627956 KB Output is correct
80 Correct 1872 ms 776276 KB Output is correct
81 Correct 1164 ms 604916 KB Output is correct
82 Correct 1515 ms 714824 KB Output is correct
83 Correct 1969 ms 807320 KB Output is correct
84 Correct 1092 ms 580920 KB Output is correct
85 Correct 2149 ms 781528 KB Output is correct
86 Correct 2083 ms 768412 KB Output is correct
87 Correct 494 ms 536164 KB Output is correct
88 Correct 763 ms 657256 KB Output is correct
89 Correct 768 ms 657496 KB Output is correct
90 Correct 757 ms 657504 KB Output is correct