QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#459438 | #8831. Chemistry Class | ucup-team3695# | WA | 73ms | 15856kb | C++20 | 2.1kb | 2024-06-30 03:55:10 | 2024-06-30 03:55:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define pb push_back
#define mp make_pair
struct Tree {
typedef int T;
static constexpr T unit = INT_MIN;
T f(T a, T b) { return max(a, b); } // (any associative fn)
vector<T> s; int n;
Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
void update(int pos, T val) {
for (s[pos += n] = val; pos /= 2;)
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
T query(int b, int e) { // query [b, e)
T ra = unit, rb = unit;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) ra = f(ra, s[b++]);
if (e % 2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
};
#define MAXN 400'010
int n;
ll t1, t2;
ll a[MAXN];
ll b[MAXN];
ll d[MAXN];
int memo[MAXN];
int earliest[MAXN];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int t;
cin >> t;
while (t--) {
cin >> n >> t1 >> t2;
rep(i, 0, 2*n) cin >> d[i];
sort(d, d+2*n);
rep(i, 0, n) {
a[i] = d[2*i];
b[i] = d[2*i+1];
}
int ind = 0;
bool bad = false;
rep(i, 0, n) {
if (b[i] > a[i] + t1) {
bad = true;
break;
}
while (b[i] > a[ind] + t1) ind++;
earliest[i] = ind;
//cout << i << ' ' << ind << endl;
}
if (bad) {
cout << -1 << '\n';
continue;
}
// match a's with b's
Tree rt(n);
int offcyclecnt = 0;
memo[0] = 0;
rep(i, 0, n) {
// match b[i] with a[0, ..., i]?
memo[i+1] = memo[i];
if (b[i] <= a[i] + t2) memo[i+1]++;
//cout << "try one " << memo[i+1] << endl;
// try matching
int best = rt.query(earliest[i], i) + offcyclecnt;
memo[i+1] = max(memo[i+1], best);
rt.update(i, memo[i] - offcyclecnt);
//cout << i << ' ' << memo[i+1] << ' ' << memo[i+1] - offcyclecnt << endl;
if (i != n-1 && b[i] >= a[i+1] - t1) {
offcyclecnt++;
}
}
cout << memo[n] << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9764kb
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: 73ms
memory: 15856kb
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'