#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int MAXN = 200200;
const int INF = 1e9;
// range add - range min
struct segtree
{
static const int DEPTH = 18;
static const int N = 1 << DEPTH;
int dsum[2 * N];
pair<int, int> rmin[2 * N];
void init()
{
fill(dsum, dsum + 2 * N, 0);
for (int i = 0; i < N; ++i) rmin[i + N] = make_pair(0, i);
for (int i = N - 1; i >= 1; --i) rmin[i] = min(rmin[2 * i], rmin[2 * i + 1]);
}
void add(int p, int qL, int qR, int depth, int v)
{
int pL = p << depth, pR = (p + 1) << depth;
if (qR <= pL || pR <= qL) return;
if (qL <= pL && pR <= qR) {
dsum[p] += v;
rmin[p].first += v;
return;
}
add(p * 2, qL, qR, depth - 1, v);
add(p * 2 + 1, qL, qR, depth - 1, v);
rmin[p] = min(rmin[p * 2], rmin[p * 2 + 1]);
rmin[p].first += dsum[p];
}
void add(int qL, int qR, int v)
{
add(1, qL + N, qR + N, DEPTH, v);
}
pair<int, int> query(int p, int qL, int qR, int depth)
{
int pL = p << depth, pR = (p + 1) << depth;
if (qR <= pL || pR <= qL) return make_pair(INF, INF);
if (qL <= pL && pR <= qR) return rmin[p];
dsum[p * 2] += dsum[p];
rmin[p * 2].first += dsum[p];
dsum[p * 2 + 1] += dsum[p];
rmin[p * 2 + 1].first += dsum[p];
dsum[p] = 0;
return min(query(p * 2, qL, qR, depth - 1), query(p * 2 + 1, qL, qR, depth - 1));
}
pair<int, int> query(int qL, int qR)
{
return query(1, qL + N, qR + N, DEPTH);
}
};
int N, A[MAXN], B[MAXN], C[MAXN], D[MAXN];
set<int> unmet[MAXN];
set<int> unusedA, unusedC;
segtree seg;
long long total_op_size = 0;
void connect(int a, int c)
{
int ai = lower_bound(D, D + N, B[a]) - D;
seg.add(ai, c, -1);
total_op_size += c - ai;
}
void dissolve(int X)
{
for (;;) {
auto m = seg.query(0, X);
if (m.first != 0) break;
while (unusedC.size() > 0 && *(unusedC.begin()) <= m.second) {
int a = *(unusedA.begin());
int c = *(unusedC.begin());
unusedA.erase(unusedA.begin());
unusedC.erase(unusedC.begin());
unmet[A[a]].erase(a);
connect(a, c);
}
seg.add(m.second, m.second + 1, INF);
}
}
int main()
{
scanf("%d", &N);
for (int i = N - 1; i >= 0; --i) scanf("%d%d", A + i, B + i);
for (int i = N - 1; i >= 0; --i) scanf("%d%d", C + i, D + i);
seg.init();
vector<pair<int, int> > eves;
for (int i = 0; i < N; ++i) {
eves.push_back({ B[i], i });
eves.push_back({ D[i], i + N });
}
sort(eves.begin(), eves.end());
int cnt = 0, d_idx = 0;
int ret = N;
for (auto p : eves) {
if (p.second < N) {
unmet[A[p.second]].insert(p.second);
unusedA.insert(p.second);
++cnt;
} else {
--cnt;
p.second -= N;
seg.add(p.second, p.second + 1, cnt);
if (unmet[C[p.second]].size() > 0) {
auto it = unmet[C[p.second]].end();
--it;
int a = *it;
unmet[C[p.second]].erase(it);
unusedA.erase(a);
connect(a, p.second);
--ret;
} else {
unusedC.insert(p.second);
}
dissolve(++d_idx);
}
}
printf("%d\n", ret);
return 0;
}
Compilation message
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
worst_reporter2.cpp:98:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = N - 1; i >= 0; --i) scanf("%d%d", A + i, B + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:99:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = N - 1; i >= 0; --i) scanf("%d%d", C + i, D + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
15864 KB |
Output is correct |
2 |
Correct |
17 ms |
16048 KB |
Output is correct |
3 |
Correct |
15 ms |
16048 KB |
Output is correct |
4 |
Correct |
15 ms |
16080 KB |
Output is correct |
5 |
Correct |
16 ms |
16080 KB |
Output is correct |
6 |
Correct |
15 ms |
16196 KB |
Output is correct |
7 |
Correct |
16 ms |
16196 KB |
Output is correct |
8 |
Correct |
17 ms |
16196 KB |
Output is correct |
9 |
Correct |
17 ms |
16196 KB |
Output is correct |
10 |
Correct |
16 ms |
16196 KB |
Output is correct |
11 |
Correct |
16 ms |
16196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
15864 KB |
Output is correct |
2 |
Correct |
17 ms |
16048 KB |
Output is correct |
3 |
Correct |
15 ms |
16048 KB |
Output is correct |
4 |
Correct |
15 ms |
16080 KB |
Output is correct |
5 |
Correct |
16 ms |
16080 KB |
Output is correct |
6 |
Correct |
15 ms |
16196 KB |
Output is correct |
7 |
Correct |
16 ms |
16196 KB |
Output is correct |
8 |
Correct |
17 ms |
16196 KB |
Output is correct |
9 |
Correct |
17 ms |
16196 KB |
Output is correct |
10 |
Correct |
16 ms |
16196 KB |
Output is correct |
11 |
Correct |
16 ms |
16196 KB |
Output is correct |
12 |
Correct |
16 ms |
16196 KB |
Output is correct |
13 |
Correct |
16 ms |
16196 KB |
Output is correct |
14 |
Correct |
17 ms |
16196 KB |
Output is correct |
15 |
Correct |
15 ms |
16196 KB |
Output is correct |
16 |
Correct |
16 ms |
16196 KB |
Output is correct |
17 |
Correct |
16 ms |
16196 KB |
Output is correct |
18 |
Correct |
16 ms |
16196 KB |
Output is correct |
19 |
Correct |
16 ms |
16196 KB |
Output is correct |
20 |
Correct |
15 ms |
16196 KB |
Output is correct |
21 |
Correct |
16 ms |
16196 KB |
Output is correct |
22 |
Correct |
16 ms |
16196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
15864 KB |
Output is correct |
2 |
Correct |
17 ms |
16048 KB |
Output is correct |
3 |
Correct |
15 ms |
16048 KB |
Output is correct |
4 |
Correct |
15 ms |
16080 KB |
Output is correct |
5 |
Correct |
16 ms |
16080 KB |
Output is correct |
6 |
Correct |
15 ms |
16196 KB |
Output is correct |
7 |
Correct |
16 ms |
16196 KB |
Output is correct |
8 |
Correct |
17 ms |
16196 KB |
Output is correct |
9 |
Correct |
17 ms |
16196 KB |
Output is correct |
10 |
Correct |
16 ms |
16196 KB |
Output is correct |
11 |
Correct |
16 ms |
16196 KB |
Output is correct |
12 |
Correct |
16 ms |
16196 KB |
Output is correct |
13 |
Correct |
16 ms |
16196 KB |
Output is correct |
14 |
Correct |
17 ms |
16196 KB |
Output is correct |
15 |
Correct |
15 ms |
16196 KB |
Output is correct |
16 |
Correct |
16 ms |
16196 KB |
Output is correct |
17 |
Correct |
16 ms |
16196 KB |
Output is correct |
18 |
Correct |
16 ms |
16196 KB |
Output is correct |
19 |
Correct |
16 ms |
16196 KB |
Output is correct |
20 |
Correct |
15 ms |
16196 KB |
Output is correct |
21 |
Correct |
16 ms |
16196 KB |
Output is correct |
22 |
Correct |
16 ms |
16196 KB |
Output is correct |
23 |
Correct |
30 ms |
16484 KB |
Output is correct |
24 |
Correct |
28 ms |
16612 KB |
Output is correct |
25 |
Correct |
29 ms |
16704 KB |
Output is correct |
26 |
Correct |
27 ms |
16804 KB |
Output is correct |
27 |
Correct |
30 ms |
17280 KB |
Output is correct |
28 |
Correct |
30 ms |
17280 KB |
Output is correct |
29 |
Correct |
28 ms |
17280 KB |
Output is correct |
30 |
Correct |
28 ms |
17280 KB |
Output is correct |
31 |
Correct |
26 ms |
17280 KB |
Output is correct |
32 |
Correct |
29 ms |
17564 KB |
Output is correct |
33 |
Correct |
34 ms |
17564 KB |
Output is correct |
34 |
Correct |
29 ms |
17564 KB |
Output is correct |
35 |
Correct |
26 ms |
17564 KB |
Output is correct |
36 |
Correct |
28 ms |
17596 KB |
Output is correct |
37 |
Correct |
27 ms |
17920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
15864 KB |
Output is correct |
2 |
Correct |
17 ms |
16048 KB |
Output is correct |
3 |
Correct |
15 ms |
16048 KB |
Output is correct |
4 |
Correct |
15 ms |
16080 KB |
Output is correct |
5 |
Correct |
16 ms |
16080 KB |
Output is correct |
6 |
Correct |
15 ms |
16196 KB |
Output is correct |
7 |
Correct |
16 ms |
16196 KB |
Output is correct |
8 |
Correct |
17 ms |
16196 KB |
Output is correct |
9 |
Correct |
17 ms |
16196 KB |
Output is correct |
10 |
Correct |
16 ms |
16196 KB |
Output is correct |
11 |
Correct |
16 ms |
16196 KB |
Output is correct |
12 |
Correct |
16 ms |
16196 KB |
Output is correct |
13 |
Correct |
16 ms |
16196 KB |
Output is correct |
14 |
Correct |
17 ms |
16196 KB |
Output is correct |
15 |
Correct |
15 ms |
16196 KB |
Output is correct |
16 |
Correct |
16 ms |
16196 KB |
Output is correct |
17 |
Correct |
16 ms |
16196 KB |
Output is correct |
18 |
Correct |
16 ms |
16196 KB |
Output is correct |
19 |
Correct |
16 ms |
16196 KB |
Output is correct |
20 |
Correct |
15 ms |
16196 KB |
Output is correct |
21 |
Correct |
16 ms |
16196 KB |
Output is correct |
22 |
Correct |
16 ms |
16196 KB |
Output is correct |
23 |
Correct |
30 ms |
16484 KB |
Output is correct |
24 |
Correct |
28 ms |
16612 KB |
Output is correct |
25 |
Correct |
29 ms |
16704 KB |
Output is correct |
26 |
Correct |
27 ms |
16804 KB |
Output is correct |
27 |
Correct |
30 ms |
17280 KB |
Output is correct |
28 |
Correct |
30 ms |
17280 KB |
Output is correct |
29 |
Correct |
28 ms |
17280 KB |
Output is correct |
30 |
Correct |
28 ms |
17280 KB |
Output is correct |
31 |
Correct |
26 ms |
17280 KB |
Output is correct |
32 |
Correct |
29 ms |
17564 KB |
Output is correct |
33 |
Correct |
34 ms |
17564 KB |
Output is correct |
34 |
Correct |
29 ms |
17564 KB |
Output is correct |
35 |
Correct |
26 ms |
17564 KB |
Output is correct |
36 |
Correct |
28 ms |
17596 KB |
Output is correct |
37 |
Correct |
27 ms |
17920 KB |
Output is correct |
38 |
Correct |
650 ms |
32424 KB |
Output is correct |
39 |
Correct |
603 ms |
37120 KB |
Output is correct |
40 |
Correct |
627 ms |
44516 KB |
Output is correct |
41 |
Correct |
488 ms |
46644 KB |
Output is correct |
42 |
Correct |
804 ms |
69580 KB |
Output is correct |
43 |
Correct |
572 ms |
69580 KB |
Output is correct |
44 |
Correct |
505 ms |
69580 KB |
Output is correct |
45 |
Correct |
530 ms |
69580 KB |
Output is correct |
46 |
Correct |
411 ms |
69580 KB |
Output is correct |
47 |
Correct |
744 ms |
77048 KB |
Output is correct |
48 |
Correct |
534 ms |
77048 KB |
Output is correct |
49 |
Correct |
579 ms |
77048 KB |
Output is correct |
50 |
Correct |
554 ms |
77048 KB |
Output is correct |
51 |
Correct |
541 ms |
77048 KB |
Output is correct |
52 |
Correct |
664 ms |
77048 KB |
Output is correct |