oj.uz

Submission #887983

# Submission time Handle Problem Language Result Execution time Memory
887983 2023-12-15T16:27:07 Z abczz Rectangles (IOI19_rect) C++14
23 / 100
 3442 ms 441104 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 64 ms 293856 KB Output is correct
2 Correct 64 ms 293972 KB Output is correct
3 Correct 63 ms 293972 KB Output is correct
4 Correct 62 ms 293980 KB Output is correct
5 Correct 62 ms 293960 KB Output is correct
6 Correct 63 ms 293980 KB Output is correct
7 Correct 62 ms 293980 KB Output is correct
8 Incorrect 62 ms 293876 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 293856 KB Output is correct
2 Correct 64 ms 293972 KB Output is correct
3 Correct 63 ms 293972 KB Output is correct
4 Correct 62 ms 293980 KB Output is correct
5 Correct 62 ms 293960 KB Output is correct
6 Correct 63 ms 293980 KB Output is correct
7 Correct 62 ms 293980 KB Output is correct
8 Incorrect 62 ms 293876 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 293856 KB Output is correct
2 Correct 64 ms 293972 KB Output is correct
3 Correct 63 ms 293972 KB Output is correct
4 Correct 62 ms 293980 KB Output is correct
5 Correct 62 ms 293960 KB Output is correct
6 Correct 63 ms 293980 KB Output is correct
7 Correct 62 ms 293980 KB Output is correct
8 Incorrect 62 ms 293876 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 293856 KB Output is correct
2 Correct 64 ms 293972 KB Output is correct
3 Correct 63 ms 293972 KB Output is correct
4 Correct 62 ms 293980 KB Output is correct
5 Correct 62 ms 293960 KB Output is correct
6 Correct 63 ms 293980 KB Output is correct
7 Correct 62 ms 293980 KB Output is correct
8 Incorrect 62 ms 293876 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 64 ms 294220 KB Output is correct
2 Correct 64 ms 294232 KB Output is correct
3 Correct 64 ms 294124 KB Output is correct
4 Correct 62 ms 293712 KB Output is correct
5 Correct 65 ms 294224 KB Output is correct
6 Correct 66 ms 294224 KB Output is correct
7 Correct 65 ms 294228 KB Output is correct
8 Correct 65 ms 294280 KB Output is correct
9 Correct 65 ms 294224 KB Output is correct
10 Correct 64 ms 294216 KB Output is correct
11 Correct 64 ms 294224 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 293972 KB Output is correct
2 Correct 1474 ms 361612 KB Output is correct
3 Correct 3218 ms 440412 KB Output is correct
4 Correct 3385 ms 441072 KB Output is correct
5 Correct 3442 ms 441104 KB Output is correct
6 Correct 1104 ms 318400 KB Output is correct
7 Correct 2118 ms 340460 KB Output is correct
8 Correct 2333 ms 343276 KB Output is correct
9 Correct 69 ms 293712 KB Output is correct
10 Correct 70 ms 293712 KB Output is correct
11 Correct 71 ms 293972 KB Output is correct
12 Correct 71 ms 293720 KB Output is correct
13 Correct 62 ms 293712 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 293856 KB Output is correct
2 Correct 64 ms 293972 KB Output is correct
3 Correct 63 ms 293972 KB Output is correct
4 Correct 62 ms 293980 KB Output is correct
5 Correct 62 ms 293960 KB Output is correct
6 Correct 63 ms 293980 KB Output is correct
7 Correct 62 ms 293980 KB Output is correct
8 Incorrect 62 ms 293876 KB Output isn't correct
9 Halted 0 ms 0 KB -