QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#459563#8831. Chemistry Classucup-team1231#WA 61ms8956kbC++141.0kb2024-06-30 07:51:282024-06-30 07:51:29

Judging History

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

  • [2024-06-30 07:51:29]
  • 评测
  • 测评结果:WA
  • 用时:61ms
  • 内存:8956kb
  • [2024-06-30 07:51:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;

int n, dp[200005];
LL A, B, a[400005];

pair<int, int> que[200005];
int fr, rr;
void qpush(int v, int i) {
    while(fr < rr && que[rr - 1].first >= v) rr--;
    que[rr++] = make_pair(v, i);
}
void qpop(int i) {
    if(fr < rr && que[fr].second == i) fr++;
}
int qtop() {
    return fr == rr ? INF : que[fr].first;
}
void solve() {
    scanf("%d%lld%lld", &n, &A, &B);
    for(int i = 0; i < 2 * n; i++) scanf("%lld", &a[i]);
    sort(a, a + 2 * n);

    fr = rr = 0;
    dp[0] = 0;
    int l = 0;
    for(int i = 0; i < n; i++) {
        qpush(dp[i], i);
        
        dp[i + 1] = a[2 * i + 1] - a[2 * i] <= B ? dp[i] : INF;
        while(l <= i && a[2 * i + 1] - a[2 * l] > A) qpop(l++);
        dp[i + 1] = min(dp[i + 1], qtop() + 1);
    }
    printf("%d\n", dp[n] == INF ? -1 : n - dp[n]);
}

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

详细

Test #1:

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

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: 61ms
memory: 8956kb

input:

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

output:

185076

result:

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