oj.uz

Submission #1047916

# Submission time Handle Problem Language Result Execution time Memory
1047916 2024-08-07T17:29:30 Z dozer Rectangles (IOI19_rect) C++14
0 / 100
 1200 ms 351764 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 2505
#define LOGN 12

vector<pii> rng_h[MAXN], rng_v[MAXN];
vector<int> hor[MAXN][MAXN], ver[MAXN][MAXN];

void compute(vector<vector<int>> &a, int t){
	int n = a.size(), m = a.front().size();
	if (t == 1) swap(n, m);
	for (int i = 1; i < n - 1; i++){
		
		set<int> s;
		vector<int> v(m);
		iota(v.begin(), v.end(), 0);
		sort(v.begin(), v.end(), [&](int x, int y){
			if (t == 0){
				if (a[i][x] == a[i][y]) return x < y;
				return a[i][x] > a[i][y];
			}
			else{
				if (a[x][i] == a[y][i]) return x < y;
				return a[x][i] > a[y][i];
			}
		});
		
		int it = 0;
		while(it < m){
			vector<int> tmp;
			int last = 0;
			if (t) last = a[v[it]][i];
			else last = a[i][v[it]];
			while(it < m){
				if (t == 0 && a[i][v[it]] != last) break;
				else if (t == 1 && a[v[it]][i] != last) break;
				tmp.pb(v[it]);
				it++;
			}
			
			for (int j = 0; j < tmp.size(); j++){
				int x = tmp[j];
				auto it2 = s.lower_bound(x);
				int prv = -1, nxt = m + 1;
				if (j > 0) prv = tmp[j - 1];
				if (j + 1 < tmp.size()) nxt = tmp[j + 1];
				
				if (it2 != s.begin() && !s.empty()){
					it2--;
					
					if (x - 1 > *it2) {
						if (t == 0) rng_h[i].pb({*it2 + 1, x - 1});
						else rng_v[i].pb({*it2 + 1, x - 1});
					}
				}
				it2 = s.lower_bound(x);
				if (it2 != s.end()){
					if (*it2 > x + 1 && *it2 < nxt) {
						
						if (t == 0) rng_h[i].pb({x + 1, *it2 - 1});
						else rng_v[i].pb({x + 1, *it2 - 1});
					}
				}
				
				s.insert(x);
			}
		}
		
	}
}


int b_search(vector<int> &v, int pos){
	int ans = pos;
	for (int i = LOGN; i >= 0; i--){
		int tmp = ans + (1<<i);
		if (tmp >= v.size()) continue;
		if (v[tmp] - v[pos] == tmp - pos) ans = tmp;
	}
	return ans;
}



long long count_rectangles(vector<vector<int>> a){
	compute(a, 0);
	compute(a, 1);
	
	int n = a.size(), m = a.front().size();
	for (int i = 1; i < n - 1; i++){
		sort(rng_h[i].begin(), rng_h[i].end());
		
		for (auto j : rng_h[i]){
			hor[j.st][j.nd].pb(i);
		}
	}

	for (int i = 1; i < m - 1; i++){
		sort(rng_v[i].begin(), rng_v[i].end());
		for (auto j : rng_v[i]){
			ver[j.st][j.nd].pb(i);
		}
	}

	long long ans = 0;
	for (int i = 1; i < m - 1; i++){
		for (int j = i; j < m - 1; j++){
			for (int k = 0; k < hor[i][j].size(); k++){

				int to = b_search(hor[i][j], k) + hor[i][j][k];
				int curr = hor[i][j][k];
				int pos = lower_bound(rng_v[i].begin(), rng_v[i].end(), make_pair(curr, 0)) - rng_v[i].begin();
				while(pos < rng_v[i].size() && rng_v[i][pos].st == curr){
					int l = rng_v[i][pos].st, r = rng_v[i][pos].nd;
					int tmp = lower_bound(ver[l][r].begin(), ver[l][r].end(), i) - ver[l][r].begin();
					int to2 = b_search(ver[l][r], tmp) + ver[l][r][tmp];
					if (to2 >= j && to >= r) ans++;
					pos++;
				}
			}
		}
	}

	return ans;

	return 0;
}


/*
int main() {
	fileio();
	int n, m;
	cin>>n>>m;
	vector<vector<int>> a(n, vector<int>(m));
	for (int i = 0; i < n; i++)	{
		for (int j = 0; j < m; j++) {
			cin>>a[i][j];
		}
	}
	long long result = count_rectangles(a);

	printf("%lld\n", result);
	return 0;
}
*/

Compilation message

rect.cpp: In function 'void compute(std::vector<std::vector<int> >&, int)':
rect.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for (int j = 0; j < tmp.size(); j++){
      |                    ~~^~~~~~~~~~~~
rect.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     if (j + 1 < tmp.size()) nxt = tmp[j + 1];
      |         ~~~~~~^~~~~~~~~~~~
rect.cpp:56:9: warning: variable 'prv' set but not used [-Wunused-but-set-variable]
   56 |     int prv = -1, nxt = m + 1;
      |         ^~~
rect.cpp: In function 'int b_search(std::vector<int>&, int)':
rect.cpp:89:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   if (tmp >= v.size()) continue;
      |       ~~~~^~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |    for (int k = 0; k < hor[i][j].size(); k++){
      |                    ~~^~~~~~~~~~~~~~~~~~
rect.cpp:125:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     while(pos < rng_v[i].size() && rng_v[i][pos].st == curr){
      |           ~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 295068 KB Output is correct
2 Correct 87 ms 295160 KB Output is correct
3 Correct 88 ms 295252 KB Output is correct
4 Correct 94 ms 295248 KB Output is correct
5 Correct 88 ms 295236 KB Output is correct
6 Incorrect 64 ms 295072 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 295068 KB Output is correct
2 Correct 87 ms 295160 KB Output is correct
3 Correct 88 ms 295252 KB Output is correct
4 Correct 94 ms 295248 KB Output is correct
5 Correct 88 ms 295236 KB Output is correct
6 Incorrect 64 ms 295072 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 295068 KB Output is correct
2 Correct 87 ms 295160 KB Output is correct
3 Correct 88 ms 295252 KB Output is correct
4 Correct 94 ms 295248 KB Output is correct
5 Correct 88 ms 295236 KB Output is correct
6 Incorrect 64 ms 295072 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 295068 KB Output is correct
2 Correct 87 ms 295160 KB Output is correct
3 Correct 88 ms 295252 KB Output is correct
4 Correct 94 ms 295248 KB Output is correct
5 Correct 88 ms 295236 KB Output is correct
6 Incorrect 64 ms 295072 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 295504 KB Output is correct
2 Correct 61 ms 295508 KB Output is correct
3 Correct 60 ms 295248 KB Output is correct
4 Correct 51 ms 294996 KB Output is correct
5 Incorrect 65 ms 295516 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 295108 KB Output is correct
2 Incorrect 1200 ms 351764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 295068 KB Output is correct
2 Correct 87 ms 295160 KB Output is correct
3 Correct 88 ms 295252 KB Output is correct
4 Correct 94 ms 295248 KB Output is correct
5 Correct 88 ms 295236 KB Output is correct
6 Incorrect 64 ms 295072 KB Output isn't correct
7 Halted 0 ms 0 KB -