oj.uz

Submission #887980

# Submission time Handle Problem Language Result Execution time Memory
887980 2023-12-15T16:25:27 Z abczz Rectangles (IOI19_rect) C++14
23 / 100
 3312 ms 441436 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) {
			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]) {
					//if (i == 4 && j == 3) 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 (i == 4 && j == 3) cout << A[i][j][l][0] << " " << A[i][j][l][1] << endl;
					/*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 (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: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:87: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]
   87 |   for (int i=0; i<V.size(); ++i) {
      |                 ~^~~~~~~~~
rect.cpp:89: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]
   89 |    if (i != V.size()-1 && V[i][0] == V[i+1][0]) continue;
      |        ~~^~~~~~~~~~~~~
rect.cpp:113:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |     for (auto [u, v] : B[i][j-1]) {
      |               ^
rect.cpp:119:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |     for (auto [u, v] : B[i][j]) {
      |               ^
rect.cpp:111:9: warning: unused variable 'k' [-Wunused-variable]
  111 |     int k = 0;
      |         ^
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() && r < B[i][j].size()) {
      |           ~~^~~~~~~~~~~~~~~~
rect.cpp:133: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]
  133 |    while (l < A[i][j].size() && r < B[i][j].size()) {
      |                                 ~~^~~~~~~~~~~~~~~~
rect.cpp:149: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]
  149 |    while (l < A[i][j].size()) {
      |           ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 293968 KB Output is correct
2 Correct 62 ms 293908 KB Output is correct
3 Correct 62 ms 293860 KB Output is correct
4 Correct 65 ms 293972 KB Output is correct
5 Correct 62 ms 293772 KB Output is correct
6 Correct 63 ms 293776 KB Output is correct
7 Correct 62 ms 293760 KB Output is correct
8 Incorrect 62 ms 293908 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 293968 KB Output is correct
2 Correct 62 ms 293908 KB Output is correct
3 Correct 62 ms 293860 KB Output is correct
4 Correct 65 ms 293972 KB Output is correct
5 Correct 62 ms 293772 KB Output is correct
6 Correct 63 ms 293776 KB Output is correct
7 Correct 62 ms 293760 KB Output is correct
8 Incorrect 62 ms 293908 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 293968 KB Output is correct
2 Correct 62 ms 293908 KB Output is correct
3 Correct 62 ms 293860 KB Output is correct
4 Correct 65 ms 293972 KB Output is correct
5 Correct 62 ms 293772 KB Output is correct
6 Correct 63 ms 293776 KB Output is correct
7 Correct 62 ms 293760 KB Output is correct
8 Incorrect 62 ms 293908 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 293968 KB Output is correct
2 Correct 62 ms 293908 KB Output is correct
3 Correct 62 ms 293860 KB Output is correct
4 Correct 65 ms 293972 KB Output is correct
5 Correct 62 ms 293772 KB Output is correct
6 Correct 63 ms 293776 KB Output is correct
7 Correct 62 ms 293760 KB Output is correct
8 Incorrect 62 ms 293908 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 294216 KB Output is correct
2 Correct 71 ms 294480 KB Output is correct
3 Correct 64 ms 293976 KB Output is correct
4 Correct 62 ms 293712 KB Output is correct
5 Correct 65 ms 294228 KB Output is correct
6 Correct 65 ms 294316 KB Output is correct
7 Correct 65 ms 294224 KB Output is correct
8 Correct 72 ms 294228 KB Output is correct
9 Correct 67 ms 294228 KB Output is correct
10 Correct 62 ms 294224 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 63 ms 293716 KB Output is correct
2 Correct 1504 ms 361608 KB Output is correct
3 Correct 3252 ms 440716 KB Output is correct
4 Correct 3300 ms 441436 KB Output is correct
5 Correct 3312 ms 441016 KB Output is correct
6 Correct 1154 ms 318388 KB Output is correct
7 Correct 2207 ms 340280 KB Output is correct
8 Correct 2289 ms 343268 KB Output is correct
9 Correct 65 ms 293976 KB Output is correct
10 Correct 69 ms 293716 KB Output is correct
11 Correct 67 ms 293972 KB Output is correct
12 Correct 62 ms 293980 KB Output is correct
13 Correct 63 ms 293936 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 293968 KB Output is correct
2 Correct 62 ms 293908 KB Output is correct
3 Correct 62 ms 293860 KB Output is correct
4 Correct 65 ms 293972 KB Output is correct
5 Correct 62 ms 293772 KB Output is correct
6 Correct 63 ms 293776 KB Output is correct
7 Correct 62 ms 293760 KB Output is correct
8 Incorrect 62 ms 293908 KB Output isn't correct
9 Halted 0 ms 0 KB -