UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213803#2406. Thief MastersOrigami_Tobiichi1001456ms24960kbC++116.5kb2024-11-13 20:00:492024-11-13 23:04:33

answer

#include <bits/stdc++.h>
using namespace std;
namespace Octane
{
// non terrae plus ultra
#define OCTANE
#define BUFFER_SIZE 100000
#define ll long long
#define db double
#define ldb long double
	char ibuf[BUFFER_SIZE], obuf[BUFFER_SIZE];
	char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1 == p2) and (p2 = (p1 = ibuf) + fread(ibuf, 1, BUFFER_SIZE, stdin), p1 == p2) ? (EOF) : (*p1++))
#define putchar(x) ((p3 == obuf + BUFFER_SIZE) && (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf), *p3++ = x)
#endif // fread in OJ, getchar in local

#define isdigit(ch) (ch > 47 && ch < 58)
#define isspace(ch) (ch < 33 && ch != EOF)

	const ll pow10[] = {
		(ll)1e0,
		(ll)1e1,
		(ll)1e2,
		(ll)1e3,
		(ll)1e4,
		(ll)1e5,
		(ll)1e6,
		(ll)1e7,
		(ll)1e8,
		(ll)1e9,
		(ll)1e10,
		(ll)1e11,
		(ll)1e12,
		(ll)1e13,
		(ll)1e14,
		(ll)1e15,
		(ll)1e16,
		(ll)1e17,
		(ll)1e18,
	};

	struct Octane_t
	{
		~Octane_t()
		{
			fwrite(obuf, p3 - obuf, 1, stdout);
		}
		bool flag = false;
		operator bool()
		{
			return flag;
		}
	} io;

	template <typename T>
	inline T read()
	{
		T s = 0;
		int w = 1;
		char ch;
		while (ch = getchar(), !isdigit(ch) && (ch != EOF))
			if (ch == '-')
				w = -1;
		if (ch == EOF)
			return 0;
		while (isdigit(ch))
			s = s * 10 + ch - 48, ch = getchar();
		if (ch == '.')
		{
			ll flt = 0;
			int cnt = 0;
			while (ch = getchar(), isdigit(ch))
				if (cnt < 18)
					flt = flt * 10 + ch - 48, cnt++;
			s += (db)flt / pow10[cnt];
		}
		return s *= w;
	}
	template <typename T>
	inline bool read(T &s)
	{
		s = 0;
		int w = 1;
		char ch;
		while (ch = getchar(), !isdigit(ch) && (ch != EOF))
			if (ch == '-')
				w = -1;
		if (ch == EOF)
			return false;
		while (isdigit(ch))
			s = s * 10 + ch - 48, ch = getchar();
		if (ch == '.')
		{
			ll flt = 0;
			int cnt = 0;
			while (ch = getchar(), isdigit(ch))
				if (cnt < 18)
					flt = flt * 10 + ch - 48, cnt++;
			s += (db)flt / pow10[cnt];
		}
		return s *= w, true;
	}
	inline bool read(char &s)
	{
		while (s = getchar(), isspace(s))
			;
		return s != EOF;
	}
	inline bool read(char *s)
	{
		char ch;
		while (ch = getchar(), isspace(ch))
			;
		if (ch == EOF)
			return false;
		while (!isspace(ch))
			*s++ = ch, ch = getchar();
		*s = '\000';
		return true;
	}
	template <typename T>
	void print(T x)
	{
		static int t[20];
		int top = 0;
		if (x < 0)
			putchar('-'), x = -x;
		do
		{
			t[++top] = x % 10;
			x /= 10;
		} while (x);
		while (top)
			putchar(t[top--] + 48);
	}
	struct empty_type
	{
	};
	int pcs = 8;
	empty_type setpcs(int cnt)
	{
		return pcs = cnt, empty_type();
	}
	inline void print(empty_type x) {}
	inline void print(double x)
	{
		if (x < 0)
			putchar('-'), x = -x;
		x += 5.0 / pow10[pcs + 1];
		print((ll)(x));
		x -= (ll)(x);
		if (pcs != 0)
			putchar('.');
		for (int i = 1; i <= pcs; i++)
			x *= 10, putchar((int)x + '0'), x -= (int)x;
	}
	inline void print(float x)
	{
		if (x < 0)
			putchar('-'), x = -x;
		x += 5.0 / pow10[pcs + 1];
		print((ll)(x));
		x -= (ll)(x);
		if (pcs != 0)
			putchar('.');
		for (int i = 1; i <= pcs; i++)
			x *= 10, putchar((int)x + '0'), x -= (int)x;
	}
	inline void print(char x)
	{
		putchar(x);
	}
	inline void print(char *x)
	{
		for (int i = 0; x[i]; i++)
			putchar(x[i]);
	}
	inline void print(const char *x)
	{
		for (int i = 0; x[i]; i++)
			putchar(x[i]);
	}

// support for string
#ifdef _GLIBCXX_STRING
	inline bool read(std::string &s)
	{
		s = "";
		char ch;
		while (ch = getchar(), isspace(ch))
			;
		if (ch == EOF)
			return false;
		while (!isspace(ch))
			s += ch, ch = getchar();
		return true;
	}
	inline void print(std::string x)
	{
		for (string::iterator i = x.begin(); i != x.end(); i++)
			putchar(*i);
	}
	inline bool getline(Octane_t &io, string s)
	{
		s = "";
		char ch = getchar();
		if (ch == EOF)
			return false;
		while (ch != '\n' and ch != EOF)
			s += ch, ch = getchar();
		return true;
	}
#endif

// support for initializer_list
#if __cplusplus >= 201103L
	template <typename T, typename... T1>
	inline int read(T &a, T1 &...other)
	{
		return read(a) + read(other...);
	}
	template <typename T, typename... T1>
	inline void print(T a, T1... other)
	{
		print(a);
		print(other...);
	}
#endif

	//  give up iostream
	template <typename T>
	Octane_t &operator>>(Octane_t &io, T &b)
	{
		return io.flag = read(b), io;
	}
	Octane_t &operator>>(Octane_t &io, char *b)
	{
		return io.flag = read(b), io;
	}
	template <typename T>
	Octane_t &operator<<(Octane_t &io, T b)
	{
		return print(b), io;
	}

#define cout io
#define cin io
#define endl '\n'
#undef ll
#undef db
#undef ldb
#undef BUFFER_SIZE
}
using namespace Octane;
#define file(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define int long long
const int N = 1e3 + 10;
int n, m, k, ans = 1e9;
int sq[N][N], g[N][N], f[N][N];
signed main()
{
	// file();
	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			cin >> sq[i][j];
	for (int i = 1; i <= n; ++i)
	{
		list<pair<int, int>> q;
		for (int j = 1; j <= m; ++j)
		{
			while (q.size() && q.back().first <= sq[i][j])
				q.pop_back();
			while (q.size() && q.front().second <= j - k)
				q.pop_front();
			q.push_back({sq[i][j], j});
			f[i][j] = q.front().first;
		}
	}
	for (int i = 1; i <= m; ++i)
	{
		list<pair<int, int>> q;
		for (int j = 1; j <= n; ++j)
		{
			while (q.size() && q.back().first <= f[j][i])
				q.pop_back();
			while (q.size() && q.front().second <= j - k)
				q.pop_front();
			q.push_back({f[j][i], j});
			f[j][i] = max(q.front().first, f[j][i]);
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		list<pair<int, int>> q;
		for (int j = 1; j <= m; ++j)
		{
			while (q.size() && q.back().first >= sq[i][j])
				q.pop_back();
			while (q.size() && q.front().second <= j - k)
				q.pop_front();
			q.push_back({sq[i][j], j});
			g[i][j] = q.front().first;
		}
	}
	for (int i = 1; i <= m; ++i)
	{
		list<pair<int, int>> q;
		for (int j = 1; j <= n; ++j)
		{
			while (q.size() && q.back().first >= g[j][i])
				q.pop_back();
			while (q.size() && q.front().second <= j - k)
				q.pop_front();
			q.push_back({g[j][i], j});
			g[j][i] = min(q.front().first, g[j][i]);
		}
	}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
		{
			if (i < k || j < k)
				continue;
			ans = min(ans, f[i][j] - g[i][j]);
		}
	cout << ans << endl;
	return 0;
}
Source code, Language: C++11

Details

小提示：点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 325ms
memory: 24960kb

input:

1000 1000 100
804544523 340648618 718292412 235345736 704741136 942776831 741228920 463473302 677289...

output:

998893495

result:

ok single line: '998893495'

Test #2:

score: 10
Accepted
time: 0ms
memory: 1232kb

input:

5 4 2
1 2 5 6
0 17 16 0
16 17 0 1
2 10 2 1
1 2 3 2

output:

2

result:

ok single line: '2'

Test #3:

score: 10
Accepted
time: 0ms
memory: 2672kb

input:

100 100 10
2 100001 200001 300001 400001 500001 600001 700001 800001 900001 1000001 1100001 1200001 ...

output:

908999

result:

ok single line: '908999'

Test #4:

score: 10
Accepted
time: 286ms
memory: 24956kb

input:

1000 1000 20
1 100001 200001 300001 400001 500001 600001 700001 800001 900001 1000001 1100001 120000...

output:

1901899

result:

ok single line: '1901899'

Test #5:

score: 10
Accepted
time: 84ms
memory: 13108kb

input:

500 500 50
79289095 232165705 955620938 481434262 465576217 112035388 50089892 459799006 181906335 3...

output:

995944328

result:

ok single line: '995944328'

Test #6:

score: 10
Accepted
time: 152ms
memory: 13120kb

input:

500 1000 80
499163842 331022295 940054497 684192083 248823911 842132608 629298697 398526298 98438040...

output:

998299092

result:

ok single line: '998299092'

Test #7:

score: 10
Accepted
time: 268ms
memory: 24960kb

input:

1000 1000 80
102 134 429 251 299 109 264 669 727 296 112 550 270 270 544 660 131 546 968 219 113 678...

output:

998

result:

ok single line: '998'

Test #8:

score: 10
Accepted
time: 46ms
memory: 13108kb

input:

500 500 100
65532583 920409544 753795976 989349545 818384831 778207112 425141881 853270293 542112588...

output:

999172505

result:

ok single line: '999172505'

Test #9:

score: 10
Accepted
time: 104ms
memory: 13120kb

input:

500 1000 100
456896744 779471086 578349238 52507342 192194992 156396237 475084995 775765435 96617474...

output:

998801667

result:

ok single line: '998801667'

Test #10:

score: 10
Accepted
time: 191ms
memory: 24956kb

input:

1000 1000 100
629053044 957239666 456746076 940194386 201529807 592062148 244394389 825620014 223976...

output:

998862873

result:

ok single line: '998862873'

Extra Test:

score: 0
Extra Test Passed

中文 English

Server time: 2025-02-28 04:38:37 | 开源项目