QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#282141 | #1173. Knowledge Is... | ChasingLight | RE | 0ms | 0kb | C++14 | 2.2kb | 2023-12-11 14:27:32 | 2023-12-11 14:27:32 |
answer
#include <bits/stdc++.h>
int N;
class Ask {
public:
int l, r;
Ask() {
l = r = 0;
}
bool operator <(const Ask &b) const {
if (l != b.l)
return l < b.l;
else
return r < b.r;
}
}ask[510000];
class Node {
public:
int id;
Node () {
id = 0;
}
Node (int _id) {
id = _id;
}
bool operator <(const Node &b) const {
// return id > b.id;
return ask[id].r > ask[b.id].r;
}
};
std::priority_queue<Node> queue;
// class Node2 {
// public:
// int id;
// Node2 (int _id) {
// id = _id;
// }
// bool operator <(const Node2 &b) const {
// // return id > b.id;
// return ask[id].r < ask[b.id].r;
// }
// };
std::priority_queue<Node> need;
int main() {
freopen("interval.in", "r", stdin);
freopen("interval.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> N;
for (int i = 1; i <= N; ++ i)
std::cin >> ask[i].l >> ask[i].r;
std::stable_sort(ask + 1, ask + 1 + N);
// for (int i = 1; i <= N; ++ i)
// std::cout << ask[i].l << ' ' << ask[i].r << '\n';
// std::cout << -1 << '\n';
need.emplace(1);
for (int i = 2; i <= N; ++ i) {
int position = (need.size() ? need.top().id : -1);
if (position == -1 || ask[position].r > ask[i].l) {
if (!queue.size()) {
need.emplace(i);
}
else {
int min = queue.top().id;
if (ask[min].r < ask[i].r) {
queue.pop();
queue.emplace(i);
need.emplace(min);
}
else {
need.emplace(i);
}
}
}
else {
need.pop();
queue.emplace(i);
}
}
std::cout << queue.size() << '\n';
// Node a, b;
// a.id = 1, b.id = 2;
// queue.emplace(a);
// queue.emplace(b);
// std::cout << queue.top().id;
return 0;
}
详细
Test #1:
score: 0
Dangerous Syscalls
input:
7 5 9 10 7 9 3 4 9 10 2 6 8 9 5 8