QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#282141#1173. Knowledge Is...ChasingLightRE 0ms0kbC++142.2kb2023-12-11 14:27:322023-12-11 14:27:32

Judging History

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

  • [2023-12-11 14:27:32]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: