#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
int n;
const int MAXN = 2e5 + 1;
const int inf = 1e8;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
pii ev[MAXN << 1];
pii seg[1 << 19];
int lazy[1 << 19];
set<int> as, cs;
set<int> mp[MAXN];
void init(int i, int s, int e) {
seg[i].second = s;
if (s == e) return;
int m = (s + e) / 2;
init(i << 1, s, m);
init(i << 1 | 1, m + 1, e);
}
void update(int i, int s, int e, int x, int y, int v) {
if (e < x || y < s) return;
if (x <= s && e <= y) {
lazy[x] += v;
seg[i].first += v;
return;
}
int m = (s + e) / 2;
update(i << 1, s, m, x, y, v);
update(i << 1 | 1, m + 1, e, x, y, v);
seg[i] = min(seg[i << 1], seg[i << 1 | 1]);
seg[i].first += lazy[i];
}
pii query(int i, int s, int e, int x, int y) {
if (e < x || y < s) return pii(inf, -1);
if (x <= s && e <= y) return seg[i];
int m = (s + e) / 2;
pii ret = min(query(i << 1, s, m, x, y), query(i << 1 | 1, m + 1, e, x, y));
ret.first += lazy[i];
return ret;
}
void newMatching(int ax, int cx) {
int x = lower_bound(d, d + n, b[ax]) - d;
update(1, 0, n - 2, x, cx - 1, -1);
}
int main() {
scanf("%d", &n);
for (int i = n; i--; ) {
scanf("%d%d", a + i, b + i);
ev[i] = { b[i], i };
}
for (int i = n; i--; ) {
scanf("%d%d", c + i, d + i);
ev[i + n] = { d[i], i + n };
}
sort(ev, ev + (n << 1));
int cnt = 0, ans = 0;
for (int i = 0; i < (n << 1); ++i) {
int sc, x;
tie(sc, x) = ev[i];
if (x < n) {
++cnt;
mp[a[x]].insert(x);
as.insert(x);
}
else {
x -= n;
update(1, 0, n - 2, x, x, --cnt);
if (mp[c[x]].empty()) {
cs.insert(x);
}
else {
++ans;
int ax = *mp[c[x]].rbegin();
mp[c[x]].erase(ax);
as.erase(ax);
newMatching(ax, x);
}
while (1) {
pii ret = query(1, 0, n - 2, 0, x);
if (ret.first) break;
int t = ret.second, cx;
set<int>::iterator it;
while (!cs.empty() && (cx = *cs.begin()) <= t) {
int ax = *as.begin();
as.erase(ax);
cs.erase(cx);
mp[a[ax]].erase(ax);
newMatching(ax, cx);
}
update(1, 0, n - 1, t, t, inf);
}
}
}
printf("%d\n", n - ans);
return 0;
}
Compilation message
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
worst_reporter2.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", a + i, b + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", c + i, d + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
