oj.uz

Submission #321715

# Submission time Handle Problem Language Result Execution time Memory
321715 2020-11-13T05:17:12 Z Kevin_Zhang_TW The Kingdom of JOIOI (JOI17_joioi) C++17
15 / 100
 4000 ms 5460 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template <class T, class ...U> 
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template <class T>
void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

template <class T>
bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
template <class T>
bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int MAX_N = 2010, inf = 1e9;
#define int ll
int n, m, a[MAX_N][MAX_N], res = inf;
struct bit {
	vector<vector<int>> v;
	int n, m;
	bit(int _n, int _m) :
		n(_n), m(_m) {
			v.resize(n+1, vector<int>(m+1)); 
		}

	void add(int x, int y) {
		++v[x][y];
//		for (int i = x;i <= n;i += i&-i)
//		   for (int j = y;j <= m;j += j&-j)
//			   ++v[i][j];
	}
	int qry(int x, int y) {
		int res = 0;
		for (int i = 1;i <= x;++i)
			for (int j = 1;j <= y;++j)
				res += v[i][j];
		return res;
		for (int i = x;i;i ^= i&-i)
			for (int j = y;j;j ^= j&-j)
				res += v[i][j];
		return res;
	}
};
		   		   
void update() {
	bit tree(n, m);
	DE(n, m);
	for (int i = 1;i <= n;++i)
		debug(a[i]+1, a[i]+1+m);
	cerr << '\n';

	vector<pair<int,int>> id;
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j)
			id.pb(i, j);

	auto get = [&](pair<int,int> p) {
		return a[p.first][p.second];
	};

	sort(AI(id), [&](auto x, auto y) {
			return get(x) < get(y);
			});

	auto valid = [&](pair<int,int> p) {
		assert(tree.qry(p.first, p.second) <= p.first * p.second);
		return tree.qry(p.first, p.second) == p.first * p.second;
	};

	for (int i = 0, j = 0;i+1 < id.size();++i) {
		tree.add(id[i].first, id[i].second);

		while (j <= i && valid(id[j]))
			++j;
		//DE(get(id[i]), get(id[0]));

		if (valid(id[0]) && valid(id[i]))
			chmin(res, max(get(id[i]) - get(id[0]), get(id.back()) - get(id[j])));
	}
	chmin(res, get(id.back()) - get(id.front()));
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j)
			cin >> a[i][j];
	update();

	for (int l = 1, r = n;l < r;++l, --r)
		swap(a[l], a[r]);

	update();

	for (int i = 1;i <= n;++i) {
		for (int l = 1, r = m;l < r;++l, --r)
			swap(a[i][l], a[i][r]);
	}

	update();
	for (int l = 1, r = n;l < r;++l, --r)
		swap(a[l], a[r]);
	update();

	cout << res << '\n';
}

Compilation message

joioi.cpp: In function 'void update()':
joioi.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
joioi.cpp:55:2: note: in expansion of macro 'DE'
   55 |  DE(n, m);
      |  ^~
joioi.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
joioi.cpp:57:3: note: in expansion of macro 'debug'
   57 |   debug(a[i]+1, a[i]+1+m);
      |   ^~~~~
joioi.cpp:78:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 0, j = 0;i+1 < id.size();++i) {
      |                        ~~~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 620 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 27 ms 620 KB Output is correct
16 Execution timed out 4081 ms 5460 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 27 ms 620 KB Output is correct
16 Execution timed out 4081 ms 5460 KB Time limit exceeded
17 Halted 0 ms 0 KB -