QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#457675#8831. Chemistry Classucup-team266#WA 13ms9572kbC++142.5kb2024-06-29 13:38:142024-06-29 13:38:15

Judging History

你现在查看的是最新测评结果

  • [2024-06-29 13:38:15]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:9572kb
  • [2024-06-29 13:38:14]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int Mod = 1e9 + 7;
inline void uadd(int &a, const int &b){ a += b - Mod; a += (a>>31) & Mod; }
inline int add(int a, const int &b){ a += b - Mod; a += (a>>31) & Mod; return a; }
inline void usub(int &a, const int &b){ a -= b; a += (a>>31) & Mod; }
inline int sub(int a, const int &b){ a -= b, a += (a>>31) & Mod; return a; }
inline void umul(int &a, const int &b){ a = (int)(1ll * a * b % Mod); }
inline int mul(const int &a, const int &b){ return (int)(1ll * a * b % Mod); }
int qpow(int b, ll p){ int ret = 1; while(p){ if(p & 1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 100;
int fact[fN], invfact[fN];
void initfact(int n){
	fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i - 1], i);
	invfact[n] = qpow(fact[n], Mod - 2); for(int i = n; i >= 1; --i) invfact[i - 1] = mul(invfact[i], i);
}
inline int binom(int n, int m){
	//cout << "binom " << n << " " << m << " = " << mul(fact[n], mul(invfact[m], invfact[n - m])) << endl;
	return mul(fact[n], mul(invfact[m], invfact[n - m]));
}
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
template<typename T> inline void chmax(T &_a, const T &_b){ (_b>_a) ? (_a=_b) : _a; }
template<typename T> inline void chmin(T &_a, const T &_b){ (_b<_a) ? (_a=_b) : _a; }

int n, A, B, a[400400];

int f[400400], sum[400400];

void solve(){
	cin >> n >> A >> B;
	n *= 2;
	rep(i, n) cin >> a[i];
	sort(a, a + n);
	for(int i = 0; i < n; i += 2) if(a[i + 1] - a[i] > A){
		cout << "-1\n";
		return ;
	}

	sum[1] = 0;
	for(int i = 3; i < n; i += 2){
		sum[i] = sum[i - 2] + (a[i - 1] - a[i - 2] <= B) - ((a[i - 1] - a[i - 2] > A) ? inf : 0);
	}
	static int que[400400]; int hd = 0, rr = 0;
	f[0] = 0, que[rr++] = 0;
	for(int i = 1; i < n; i += 2){
		f[i + 1] = -inf;
		int p = (int)(lower_bound(a, a + n, a[i] - A) - a);
		while(que[hd] < p) ++hd;
		f[i + 1] = f[que[hd]] + sum[i] - sum[que[hd] + 1];
		if(a[i] - a[i - 1] <= B) chmax(f[i + 1], f[i - 1] + 1);
		while(rr > hd && f[que[rr - 1]] - sum[que[rr - 1] + 1] < f[i + 1] - sum[i + 1 + 1]) --rr;
		que[rr++] = i + 1;
		//for(int j = i - 1; j >= p; j -= 2){
		//	chmax(f[i + 1], f[j] + sum[i] - sum[j + 1]);
		//}
	}
	cout << ((f[n] < 0) ? -1 : f[n]) << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T;
	cin >> T;
	while(T--){
		solve();
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7592kb

input:

4
1 2 1
42 69
2 3 1
1 2 3 4
2 5 1
6 1 3 4
5 19 1
1 7 8 9 10 11 12 13 14 20

output:

-1
2
1
4

result:

ok 4 number(s): "-1 2 1 4"

Test #2:

score: -100
Wrong Answer
time: 13ms
memory: 9572kb

input:

1
199996 67013419502794 1
403716252634677166 895717933735068492 410002430455111886 844431179242134559 322988383133810700 133475121268220299 481706326769800263 606871141911985391 195911124687409946 959578180866483093 930547702157856949 877914383714875160 994158366044742636 890855755285236186 69498488...

output:

199996

result:

wrong answer 1st numbers differ - expected: '0', found: '199996'