結果

問題 No.3054 Modulo Inequalities
ユーザー Zhang Letao
提出日時 2025-09-04 15:51:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,719 bytes
コンパイル時間 2,601 ms
コンパイル使用メモリ 195,128 KB
実行使用メモリ 23,092 KB
最終ジャッジ日時 2025-09-04 15:51:51
合計ジャッジ時間 8,008 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 29 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

namespace IO {
	const int maxn = 1 << 20;
	
	char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;

	inline char gc() {
		return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
	}

	template<typename T = int>
	inline T read() {
		char c = gc();
		T x = 0;
		bool f = 0;
		while (c < '0' || c > '9') {
			f |= (c == '-');
			c = gc();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c ^ 48);
			c = gc();
		}
		return f ? ~(x - 1) : x;
	}
	
	inline int reads(char *s) {
		char c = gc();
		int len = 0;
		while (isspace(c)) {
			c = gc();
		}
		while (!isspace(c) && c != -1) {
			s[len++] = c;
			c = gc();
		}
		return len;
	}

	inline void flush() {
		fwrite(obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	
	struct Flusher {
		~Flusher() {
			flush();
		}
	} AutoFlush;

	inline void pc(char ch) {
		if (oS == obuf + maxn) {
			flush();
		}
		*oS++ = ch;
	}

	template<typename T>
	inline void write(T x) {
		static char stk[64], *tp = stk;
		if (x < 0) {
			x = ~(x - 1);
			pc('-');
		}
		do {
			*tp++ = x % 10;
			x /= 10;
		} while (x);
		while (tp != stk) {
			pc((*--tp) | 48);
		}
	}
	
	template<typename T>
	inline void writesp(T x) {
		write(x);
		pc(' ');
	}
	
	template<typename T>
	inline void writeln(T x) {
		write(x);
		pc('\n');
	}
}

using IO::read;
using IO::reads;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;

const int maxn = 3000100;

int n, f[maxn], g[maxn], N;
struct node {
	int a, b;
} a[maxn];

void solve() {
	n = read();
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		a[i].a = read();
		a[i].b = read();
		++f[a[i].a];
		--f[a[i].b];
		if (a[i].a > a[i].b) {
			--f[a[i].a - a[i].b];
		} else if (a[i].a < a[i].b) {
			++g[a[i].b - a[i].a];
		}
		cnt += (a[i].a < a[i].b);
		N = max({N, a[i].a, a[i].b});
	}
	for (int i = 1; i <= N; ++i) {
		f[i] += f[i - 1];
		g[i] += g[i - 1];
	}
	int mx = 0, p = 0;
	for (int x = 1; x <= N; ++x) {
		ll t = 0;
		for (int i = 0, j, k = 0; i <= N; i = j + 1, ++k) {
			j = min(i + x - 1, N);
			t += 1LL * (f[j] - (i ? f[i - 1] : 0)) * k;
		}
		for (int i = 1, j, k = 1; i <= N; i = j + 1, ++k) {
			j = min(i + x - 1, N);
			t += 1LL * (g[j] - g[i - 1]) * k;
		}
		if (t > mx) {
			mx = t;
			p = x;
		}
	}
	if (cnt > mx) {
		mx = cnt;
		p = N + 1;
	}
	printf("%d\n", p);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}
0