oj.uz

Submission #887984

# Submission time Handle Problem Language Result Execution time Memory
887984 2023-12-15T16:27:18 Z abczz Rectangles (IOI19_rect) C++14
23 / 100
 3535 ms 441228 KB 
#include "rect.h"
#include <iostream>
#include <map>
#include <algorithm>
#include <array>
#include <vector>
#define ll long long

using namespace std;

map <ll, ll> mp;
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], n, m, f;

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) {
		mp.clear();
		V.clear();
		for (int j=0; j<m; ++j) {
			V.push_back({a[i][j], j});
		}
		sort(V.begin(), V.end(), [](auto a, auto b) {
			return a[0] > b[0];
		});
		ll p = 0;
		for (int j=0; j<V.size(); ++j) {
			mp[V[j][1]] = p;
			if (j != V.size()-1 && V[j][0] == V[j+1][0]) continue;
			else {
				while (p <= j) {
					auto it = mp.lower_bound(V[p][1]);
					if (it != mp.begin()) {
						auto pv = prev(it);
						if (pv->first+1 != it->first) {
							A[i][it->first-1].push_back({pv->first+1, i});
						}
					}
					auto nx = next(it);
					if (nx != mp.end() && it->first+1 != nx->first && it->second != nx->second) {
						A[i][nx->first-1].push_back({it->first+1, i});
					}
					++p;
				}
			}
		}
		for (int j=0; j<m; ++j) {
			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 j=0; j<m; ++j) {
		mp.clear();
		V.clear();
		for (int i=0; i<n; ++i) {
			upd[i] = -2;
			V.push_back({a[i][j], i});
		}
		sort(V.begin(), V.end(), [](auto a, auto b) {
			return a[0] > b[0];
		});
		ll p = 0;
		for (int i=0; i<V.size(); ++i) {
			mp[V[i][1]] = p;
			if (i != V.size()-1 && V[i][0] == V[i+1][0]) continue;
			else {
				while (p <= i) {
					auto it = mp.lower_bound(V[p][1]);
					if (it != mp.begin()) {
						auto pv = prev(it); 
						if (pv->first+1 != it->first) {
							upd[pv->first+1] = j;
							B[it->first-1][j].push_back({j, pv->first+1});
						}
					}
					auto nx = next(it);
					if (nx != mp.end() && it->first+1 != nx->first && it->second != nx->second) {
						upd[it->first+1] = j;
						B[nx->first-1][j].push_back({j, it->first+1});
					}
					++p;
				}
			}
		}
		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] == j) {
						upd[v] = -1;
						tmp.push_back({u, v});
					}
				}
				for (auto [u, v] : B[i][j]) {
					if (upd[v] == -1) {
						upd[v] = 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) {
			sort(B[i][j].begin(), B[i][j].end());
			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:47:18: 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]
   47 |   for (int j=0; j<V.size(); ++j) {
      |                 ~^~~~~~~~~
rect.cpp:49:10: 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]
   49 |    if (j != V.size()-1 && V[j][0] == V[j+1][0]) continue;
      |        ~~^~~~~~~~~~~~~
rect.cpp:70:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for (auto [u, v] : A[i-1][j]) {
      |               ^
rect.cpp:71: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]
   71 |      while (k < A[i][j].size()-1 && A[i][j][k][0] < u) ++k;
      |             ~~^~~~~~~~~~~~~~~~~~
rect.cpp:88:18: 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]
   88 |   for (int i=0; i<V.size(); ++i) {
      |                 ~^~~~~~~~~
rect.cpp:90:10: 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]
   90 |    if (i != V.size()-1 && V[i][0] == V[i+1][0]) continue;
      |        ~~^~~~~~~~~~~~~
rect.cpp:114:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |     for (auto [u, v] : B[i][j-1]) {
      |               ^
rect.cpp:120:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |     for (auto [u, v] : B[i][j]) {
      |               ^
rect.cpp:112:9: warning: unused variable 'k' [-Wunused-variable]
  112 |     int k = 0;
      |         ^
rect.cpp:134: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]
  134 |    while (l < A[i][j].size() && r < B[i][j].size()) {
      |           ~~^~~~~~~~~~~~~~~~
rect.cpp:134: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]
  134 |    while (l < A[i][j].size() && r < B[i][j].size()) {
      |                                 ~~^~~~~~~~~~~~~~~~
rect.cpp:144: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]
  144 |    while (l < A[i][j].size()) {
      |           ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 293968 KB Output is correct
2 Correct 63 ms 293972 KB Output is correct
3 Correct 70 ms 293972 KB Output is correct
4 Correct 69 ms 293972 KB Output is correct
5 Correct 62 ms 293712 KB Output is correct
6 Correct 64 ms 293964 KB Output is correct
7 Correct 64 ms 293968 KB Output is correct
8 Incorrect 62 ms 293788 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 293968 KB Output is correct
2 Correct 63 ms 293972 KB Output is correct
3 Correct 70 ms 293972 KB Output is correct
4 Correct 69 ms 293972 KB Output is correct
5 Correct 62 ms 293712 KB Output is correct
6 Correct 64 ms 293964 KB Output is correct
7 Correct 64 ms 293968 KB Output is correct
8 Incorrect 62 ms 293788 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 293968 KB Output is correct
2 Correct 63 ms 293972 KB Output is correct
3 Correct 70 ms 293972 KB Output is correct
4 Correct 69 ms 293972 KB Output is correct
5 Correct 62 ms 293712 KB Output is correct
6 Correct 64 ms 293964 KB Output is correct
7 Correct 64 ms 293968 KB Output is correct
8 Incorrect 62 ms 293788 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 293968 KB Output is correct
2 Correct 63 ms 293972 KB Output is correct
3 Correct 70 ms 293972 KB Output is correct
4 Correct 69 ms 293972 KB Output is correct
5 Correct 62 ms 293712 KB Output is correct
6 Correct 64 ms 293964 KB Output is correct
7 Correct 64 ms 293968 KB Output is correct
8 Incorrect 62 ms 293788 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 294408 KB Output is correct
2 Correct 65 ms 294224 KB Output is correct
3 Correct 71 ms 294212 KB Output is correct
4 Correct 66 ms 293716 KB Output is correct
5 Correct 66 ms 294340 KB Output is correct
6 Correct 67 ms 294308 KB Output is correct
7 Correct 70 ms 294356 KB Output is correct
8 Correct 66 ms 294224 KB Output is correct
9 Correct 66 ms 294228 KB Output is correct
10 Correct 69 ms 294220 KB Output is correct
11 Correct 65 ms 294100 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 293712 KB Output is correct
2 Correct 1497 ms 361336 KB Output is correct
3 Correct 3274 ms 440508 KB Output is correct
4 Correct 3535 ms 441036 KB Output is correct
5 Correct 3411 ms 441228 KB Output is correct
6 Correct 1110 ms 318368 KB Output is correct
7 Correct 2122 ms 340456 KB Output is correct
8 Correct 2252 ms 343292 KB Output is correct
9 Correct 62 ms 293764 KB Output is correct
10 Correct 61 ms 293912 KB Output is correct
11 Correct 62 ms 293972 KB Output is correct
12 Correct 62 ms 293716 KB Output is correct
13 Correct 64 ms 293776 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 293968 KB Output is correct
2 Correct 63 ms 293972 KB Output is correct
3 Correct 70 ms 293972 KB Output is correct
4 Correct 69 ms 293972 KB Output is correct
5 Correct 62 ms 293712 KB Output is correct
6 Correct 64 ms 293964 KB Output is correct
7 Correct 64 ms 293968 KB Output is correct
8 Incorrect 62 ms 293788 KB Output isn't correct
9 Halted 0 ms 0 KB -