Submission #1517985

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS  = 1e-10;
const bool debug = 0;
//----------------------//

template<typename T> struct BIT {
	vector<T> bit;
	int n;
	
	BIT() {}
	BIT(int n) : bit(vector<T>(n + 2, 0)), n(n) {}
	
	T sum(int i) {
		i++;
		T s = 0;
		while (i > 0) {
			s += bit[i];
			i -= i & -i;
		}
		return s;
	}
	
	void add(int i, T x) {
		i++;
		while (i <= n) {
			bit[i] += x;
			i += i & -i;
		}
	}
	
	T pquery(int i) {
		i++;
		return sum(i) - sum(i - 1);
	}
};

ll mod_pow(ll x, ll n, ll mod) {
	if (n == 0) return 1;
	ll res = mod_pow(x * x % mod, n / 2, mod);
	if (n & 1) res = res * x % mod;
	
	return res;
}

vector<ll> fact, inv;
void fact_inv(int n, ll mod) {
	fact.resize(n + 1);
	inv.resize(n + 1);
	
	fact[0] = 1;
	FOR(i, 1, n + 1) fact[i] = fact[i - 1] * i % mod;
	inv[n] = mod_pow(fact[n], mod - 2, mod);
	for (int i = n; i > 0; i--) inv[i - 1] = inv[i] * i % mod;
}

ll ncr(ll n, ll r, ll mod) {
	if (n < r || r < 0 || n < 0) return 0;
	return fact[n] * inv[r] % mod * inv[n - r] % mod;
}

int N, K;
int atk[112345], def[112345];
vector<int> vatk[3001];

ll solve(int d) {
	BIT<int> bit(3001);
	ll res = 0;
	
	int r = 0;
	ll last = 0;
	REP(l, 3001) {
		while (r <= 3000 && r <= l + d) {
			REP(i, vatk[r].size()) bit.add(def[vatk[r][i]], 1);
			r++;
		}
		
		ll now = 0;
		map<int, int> mm;
		REP(i, vatk[l].size()) mm[def[vatk[l][i]]]++;
		
		for (map<int, int>::iterator it = mm.begin(); it != mm.end(); ++it) {
			int ndef = it->fi;
			int tcnt = it->se;
			int cnt = bit.sum(min(ndef + d, 3000)) - bit.sum(ndef - 1);
			REP(i, tcnt) {
				ll tmp = ncr(tcnt, i + 1, MOD) * ncr(cnt - i - 1, K - i - 1, MOD) % MOD;
				if (i & 1) tmp = MOD - tmp;
				now = (now + tmp) % MOD;
			}
			
			cnt = bit.sum(ndef) - bit.sum(max(ndef - d - 1, -1));
			REP(i, tcnt) {
				ll tmp = ncr(tcnt, i + 1, MOD) * ncr(cnt - i - 1, K - i - 1, MOD) % MOD;
				if (i & 1) tmp = MOD - tmp;
				now = (now + tmp) % MOD;
			}
			
			if (tcnt >= K) now = (now + MOD - ncr(tcnt, K, MOD)) % MOD;
		}
		
		REP(i, vatk[l].size()) bit.add(def[vatk[l][i]], -1);
		
		res = (res + now) % MOD;
	}
	
	return res;
}

int main() {
	cin >> N >> K;
	REP(i, N) scanf("%d %d", atk + i, def + i);
	
	REP(i, N) vatk[atk[i]].push_back(i);
	fact_inv(N, MOD);

	int l = -1, r = 3000;
	while (r - l > 1) {
		int m = (l + r) / 2;
		if (solve(m) > 0) r = m;
		else l = m;
	}
	
	cout << r << endl;
	cout << solve(r) << endl;
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:125:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  REP(i, N) scanf("%d %d", atk + i, def + i);
                                            ^

Judge Result