oj.uz

Submission #887969

# Submission time Handle Problem Language Result Execution time Memory
887969 2023-12-15T15:51:11 Z abczz Rectangles (IOI19_rect) C++14
23 / 100
 3286 ms 441248 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;
				}
			}
			sort(B[i][j].begin(), B[i][j].end());
		}
	}
	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]) {
					//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: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:120: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]
  120 |    while (l < A[i][j].size() && r < B[i][j].size()) {
      |           ~~^~~~~~~~~~~~~~~~
rect.cpp:120: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]
  120 |    while (l < A[i][j].size() && r < B[i][j].size()) {
      |                                 ~~^~~~~~~~~~~~~~~~
rect.cpp:136: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]
  136 |    while (l < A[i][j].size()) {
      |           ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 293816 KB Output is correct
2 Correct 65 ms 293968 KB Output is correct
3 Correct 63 ms 293972 KB Output is correct
4 Correct 63 ms 293772 KB Output is correct
5 Correct 63 ms 293712 KB Output is correct
6 Incorrect 70 ms 293760 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 293816 KB Output is correct
2 Correct 65 ms 293968 KB Output is correct
3 Correct 63 ms 293972 KB Output is correct
4 Correct 63 ms 293772 KB Output is correct
5 Correct 63 ms 293712 KB Output is correct
6 Incorrect 70 ms 293760 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 293816 KB Output is correct
2 Correct 65 ms 293968 KB Output is correct
3 Correct 63 ms 293972 KB Output is correct
4 Correct 63 ms 293772 KB Output is correct
5 Correct 63 ms 293712 KB Output is correct
6 Incorrect 70 ms 293760 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 293816 KB Output is correct
2 Correct 65 ms 293968 KB Output is correct
3 Correct 63 ms 293972 KB Output is correct
4 Correct 63 ms 293772 KB Output is correct
5 Correct 63 ms 293712 KB Output is correct
6 Incorrect 70 ms 293760 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 66 ms 294384 KB Output is correct
2 Correct 66 ms 294224 KB Output is correct
3 Correct 65 ms 294212 KB Output is correct
4 Correct 63 ms 293716 KB Output is correct
5 Correct 67 ms 294260 KB Output is correct
6 Correct 66 ms 294228 KB Output is correct
7 Correct 66 ms 294384 KB Output is correct
8 Correct 66 ms 294192 KB Output is correct
9 Correct 72 ms 294228 KB Output is correct
10 Correct 64 ms 294248 KB Output is correct
11 Correct 71 ms 294224 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 293956 KB Output is correct
2 Correct 1489 ms 361532 KB Output is correct
3 Correct 3266 ms 439976 KB Output is correct
4 Correct 3257 ms 440928 KB Output is correct
5 Correct 3286 ms 441248 KB Output is correct
6 Correct 1129 ms 318552 KB Output is correct
7 Correct 2152 ms 340220 KB Output is correct
8 Correct 2308 ms 343272 KB Output is correct
9 Correct 64 ms 293708 KB Output is correct
10 Correct 62 ms 293712 KB Output is correct
11 Correct 63 ms 293976 KB Output is correct
12 Correct 65 ms 293716 KB Output is correct
13 Correct 63 ms 294060 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 293816 KB Output is correct
2 Correct 65 ms 293968 KB Output is correct
3 Correct 63 ms 293972 KB Output is correct
4 Correct 63 ms 293772 KB Output is correct
5 Correct 63 ms 293712 KB Output is correct
6 Incorrect 70 ms 293760 KB Output isn't correct
7 Halted 0 ms 0 KB -