QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#457686 | #8831. Chemistry Class | ucup-team266# | WA | 7ms | 8984kb | C++14 | 2.5kb | 2024-06-29 13:40:02 | 2024-06-29 13:40:11 |
Judging History
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);
}
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7600kb
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: 7ms
memory: 8984kb
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'