QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#282237 | #1173. Knowledge Is... | _LAP_ | WA | 0ms | 27300kb | C++14 | 1.3kb | 2023-12-11 16:42:42 | 2023-12-11 16:42:42 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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