QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#407113 | #135. Yet Another Game AI | I_Love_Sonechka | WA | 0ms | 3532kb | C++17 | 2.4kb | 2024-05-07 23:10:58 | 2024-05-07 23:10:58 |
Judging History
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'