oj.uz

Submission #887953

# Submission time Handle Problem Language Result Execution time Memory
887953 2023-12-15T15:25:10 Z abczz Rectangles (IOI19_rect) C++14
23 / 100
 3386 ms 453372 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>> A[2500][2500], B[2500][2500];
ll bit[2501], 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) {
			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) {
							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) {
						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;
				for (auto [u, v] : B[i][j-1]) {
					while (k < B[i][j].size()-1 && B[i][j][k][1] < v) ++k;
					if (B[i][j][k][1] == v) B[i][j][k][0] = u;
				}
			}
		}
	}
	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]) {
					//cout << B[i][j][r][0] << "*" << B[i][j][r][1] << endl;
					add(n-B[i][j][r][1]);
					++r;
				}
				else {
					f += query(n-A[i][j][l][1]);
					/*if (query(n-A[i][j][l][1])) {
						cout << i << " " << j << " " << query(n-A[i][j][l][1]) << '\n';
					}*/
					++l;
				}
			}
			while (l < A[i][j].size()) {
				f += query(n-A[i][j][l][1]);
				/*if (query(n-A[i][j][l][1])) {
					//cout << A[i][j][l][0] << " " << A[i][j][l][1] << endl;
					cout << i << " " << j << " " << query(n-A[i][j][l][1]) << '\n';
				}*/
				++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:46: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]
   46 |   for (int j=0; j<V.size(); ++j) {
      |                 ~^~~~~~~~~
rect.cpp:48: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]
   48 |    if (j != V.size()-1 && V[j][0] == V[j+1][0]) continue;
      |        ~~^~~~~~~~~~~~~
rect.cpp:69:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for (auto [u, v] : A[i-1][j]) {
      |               ^
rect.cpp:70: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]
   70 |      while (k < A[i][j].size()-1 && A[i][j][k][0] < u) ++k;
      |             ~~^~~~~~~~~~~~~~~~~~
rect.cpp:86: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]
   86 |   for (int i=0; i<V.size(); ++i) {
      |                 ~^~~~~~~~~
rect.cpp:88: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]
   88 |    if (i != V.size()-1 && V[i][0] == V[i+1][0]) continue;
      |        ~~^~~~~~~~~~~~~
rect.cpp:109:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |     for (auto [u, v] : B[i][j-1]) {
      |               ^
rect.cpp:110: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]
  110 |      while (k < B[i][j].size()-1 && B[i][j][k][1] < v) ++k;
      |             ~~^~~~~~~~~~~~~~~~~~
rect.cpp:119: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]
  119 |    while (l < A[i][j].size() && r < B[i][j].size()) {
      |           ~~^~~~~~~~~~~~~~~~
rect.cpp:119: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]
  119 |    while (l < A[i][j].size() && r < B[i][j].size()) {
      |                                 ~~^~~~~~~~~~~~~~~~
rect.cpp:133: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]
  133 |    while (l < A[i][j].size()) {
      |           ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 293712 KB Output is correct
2 Correct 68 ms 293956 KB Output is correct
3 Correct 67 ms 293928 KB Output is correct
4 Correct 64 ms 293972 KB Output is correct
5 Correct 73 ms 293808 KB Output is correct
6 Incorrect 63 ms 293972 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 293712 KB Output is correct
2 Correct 68 ms 293956 KB Output is correct
3 Correct 67 ms 293928 KB Output is correct
4 Correct 64 ms 293972 KB Output is correct
5 Correct 73 ms 293808 KB Output is correct
6 Incorrect 63 ms 293972 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 293712 KB Output is correct
2 Correct 68 ms 293956 KB Output is correct
3 Correct 67 ms 293928 KB Output is correct
4 Correct 64 ms 293972 KB Output is correct
5 Correct 73 ms 293808 KB Output is correct
6 Incorrect 63 ms 293972 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 293712 KB Output is correct
2 Correct 68 ms 293956 KB Output is correct
3 Correct 67 ms 293928 KB Output is correct
4 Correct 64 ms 293972 KB Output is correct
5 Correct 73 ms 293808 KB Output is correct
6 Incorrect 63 ms 293972 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 294216 KB Output is correct
2 Correct 73 ms 294328 KB Output is correct
3 Correct 64 ms 294196 KB Output is correct
4 Correct 63 ms 293716 KB Output is correct
5 Correct 67 ms 294396 KB Output is correct
6 Correct 72 ms 294308 KB Output is correct
7 Correct 68 ms 294196 KB Output is correct
8 Correct 67 ms 294264 KB Output is correct
9 Correct 69 ms 294236 KB Output is correct
10 Correct 68 ms 294236 KB Output is correct
11 Correct 67 ms 294300 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 293824 KB Output is correct
2 Correct 1612 ms 366716 KB Output is correct
3 Correct 3386 ms 452380 KB Output is correct
4 Correct 3306 ms 453028 KB Output is correct
5 Correct 3368 ms 453372 KB Output is correct
6 Correct 1110 ms 324692 KB Output is correct
7 Correct 2140 ms 351700 KB Output is correct
8 Correct 2249 ms 355508 KB Output is correct
9 Correct 63 ms 293716 KB Output is correct
10 Correct 69 ms 293768 KB Output is correct
11 Correct 63 ms 293972 KB Output is correct
12 Correct 64 ms 293932 KB Output is correct
13 Correct 63 ms 293716 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 293712 KB Output is correct
2 Correct 68 ms 293956 KB Output is correct
3 Correct 67 ms 293928 KB Output is correct
4 Correct 64 ms 293972 KB Output is correct
5 Correct 73 ms 293808 KB Output is correct
6 Incorrect 63 ms 293972 KB Output isn't correct
7 Halted 0 ms 0 KB -