QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#459438#8831. Chemistry Classucup-team3695#WA 73ms15856kbC++202.1kb2024-06-30 03:55:102024-06-30 03:55:10

Judging History

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

  • [2024-06-30 03:55:10]
  • 评测
  • 测评结果:WA
  • 用时:73ms
  • 内存:15856kb
  • [2024-06-30 03:55:10]
  • 提交

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'