QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#407113#135. Yet Another Game AII_Love_SonechkaWA 0ms3532kbC++172.4kb2024-05-07 23:10:582024-05-07 23:10:58

Judging History

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

  • [2024-05-07 23:10:58]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3532kb
  • [2024-05-07 23:10:58]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

// c++ short types
#define vt vector
typedef long long ll;
typedef long double ld;

void whattime() { cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; }
const int inf = 1e9;
const int mod = 998244353;
bool debug = false;


class SegTree {
	vt<pair<int, int>> t;
	int n;
public:
	SegTree(int _n) :n(_n) {
		t = vt<pair<int, int>>(2*n, {inf, -1});
	}
	void update(int pos, int x) {
		t[pos + n] = {x, pos};
		for(pos += n; pos > 1; pos >>= 1) {
			t[pos >> 1] = min(t[pos^1], t[pos]);
		}
	}
	int get(int l, int r) {
		pair<int, int> res = {inf, -1};
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) {
				res = min(res, t[l++]);
			}
			if(r & 1) {
				res = min(res, t[--r]);
			}
		}
		return res.second;
	}
};

void solve() {
	int n, c;
	cin >> n >> c;
	vt<pair<int, int>> s(n);
	for(int i = 0; i < n; ++i) {
//		(hp, dp)
		cin >> s[i].first >> s[i].second;
	}
	sort(s.begin(), s.end());
	vt<int> left(n), right(n);
	int j = 0, k = 0;
	for(int i = 0; i < n; ++i) {
		while(s[j].first < s[i].first - c) {
			++j;
		}
		left[i] = j;
		while(k + 1 < n and s[k+1].first <= s[i].first + c) {
			++k;
		}
		right[i] = k;
	}
	int r = 0;
	for(int i = 1; i < n; ++i) {
		if(abs(s[i].first - s[r].first) > c) {
			if(s[r].first > s[i].first) r = i;
		} else {
			if(s[r].second > s[i].second) r = i;
		}
	}
	int last = 0;
	vt<int> used(n, false);
	SegTree st(n);
	for(int i = 0; i < n; ++i) {
		st.update(i, s[i].second);
	}
	queue<int> q;
	auto Use = [&](int id, int parent = -1) {
		if(used[id]) {
			return ;
		}
		st.update(id, inf);
		used[id] = 1;
		q.push(id);
	};
	Use(r);
	while(not q.empty()) {
		int u = q.front(); q.pop();
		while(last <= left[u]) {
			Use(last, u);
			++last;
		}
		while(true) {
			auto pos = st.get(left[u], right[u] + 1);
			if(pos != -1 and s[pos].second < s[u].second and not used[pos]) {
				Use(pos, u);
			} else {
				break;
			}
		}
	}
	for(int i = 0; i < n; ++i) {
		st.update(i, s[i].second);
	}
	for(int i = 0; i < n; ++i) {
		used[i] = used[i] || s[st.get(left[i], right[i] + 1)].second >= s[i].second;
	}
	cout << accumulate(used.begin(), used.end(), 0) << "\n";
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int tt = 1;
	if(debug) {
		tt = 1e3;
	} else {
//		cin >> tt;
	}
	for(int t = 0; t < tt; ++t) {
		solve();
	}
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3532kb

input:

3 335279264
822889311 446755913
181424399 715477619
526239859 548830120

output:

2

result:

wrong answer 1st lines differ - expected: '1', found: '2'