QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#282237#1173. Knowledge Is..._LAP_WA 0ms27300kbC++141.3kb2023-12-11 16:42:422023-12-11 16:42:42

Judging History

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

  • [2023-12-11 16:42:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:27300kb
  • [2023-12-11 16:42:42]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int n, C[N]; pair<int, int> A[N];
vector<int> vec[N], lsh;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i ++) {
        int l, r; cin >> l >> r;
        A[i] = {l, r};
        lsh.emplace_back(l), lsh.emplace_back(r);
    }
    sort(lsh.begin(), lsh.end()), lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
    for(int i = 1; i <= n; i ++) {
        A[i].first = lower_bound(lsh.begin(), lsh.end(), A[i].first) - lsh.begin() + 1;
        A[i].second = lower_bound(lsh.begin(), lsh.end(), A[i].second) - lsh.begin() + 1;
        vec[A[i].first].emplace_back(A[i].second);
    }

    int res = 0, siz = 0;
    map<int, int> back;
    for(int l = 1; l <= 2 * n; l ++) {
        for(auto r : vec[l]) {
            if(siz) res ++, siz --, back[r] ++;
            else if(!back.empty() && back.begin()->first < r) {
                int u = back.begin()->first;
                back[u] --; if(!back[u]) back.erase(u);
                if(u < l) siz ++;
                else C[u] ++;
                back[r] ++;
            } else C[r] ++;
        }
        siz += C[l];
    }
    cout << res << '\n';

    return 0;
}

详细

Test #1:

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

input:

7 5
9 10
7 9
3 4
9 10
2 6
8 9
5 8

output:

3

result:

wrong output format Unexpected end of file - int32 expected