#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MN = 200010;
int N;
vector<int> V[MN], X[MN];
priority_queue<int> freeV;
multiset<int> freeX;
int Cn;
vector<int> C;
unordered_map<int, int> dc;
struct BIT {
int Z;
vector<pii> tree;
vector<int> lazy;
void init(int Z_) {
Z = Z_;
tree = vector<pii>(4 * Z);
lazy = vector<int>(4 * Z, 0);
build(0, Z - 1, 1);
}
void build(int l, int r, int n) {
if(l == r) {
tree[n] = {0, -l};
return;
}
int m = (l + r)>>1;
build(l, m, 2*n);
build(m + 1, r, 2*n + 1);
tree[n] = min(tree[2*n], tree[2*n + 1]);
}
void prop(int l, int r, int n) {
if(l != r) {
tree[2*n].first += lazy[n];
lazy[2*n] += lazy[n];
tree[2*n + 1].first += lazy[n];
lazy[2*n + 1] += lazy[n];
lazy[n] = 0;
}
}
void upd(int a, int b, int d, int l, int r, int n) {
if(b < l || r < a) return;
if(a <= l && r <= b) {
tree[n].first += d;
lazy[n] += d;
return;
}
prop(l, r, n);
int m = (l + r)>>1;
upd(a, b, d, l, m, 2*n);
upd(a, b, d, m + 1, r, 2*n + 1);
tree[n] = min(tree[2*n], tree[2*n + 1]);
}
pii quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return pii(1e9, 1e9);
if(a <= l && r <= b) return tree[n];
prop(l, r, n);
int m = (l + r)>>1;
pii L = quer(a, b, l, m, 2*n);
pii R = quer(a, b, m + 1, r, 2*n + 1);
return min(L, R);
}
void upd(int a, int b, int d) { upd(a, b, d, 0, Z - 1, 1); }
pii quer(int a, int b) { return quer(a, b, 0, Z - 1, 1); }
};
struct RMQ {
int Z;
vector<int> tree;
void init(int Z_) {
Z = Z_;
tree = vector<int>(4 * Z);
build(0, Z - 1, 1);
}
void build(int l, int r, int n) {
if(l == r) {
tree[n] = l;
return;
}
int m = (l + r)>>1;
build(l, m, 2*n);
build(m + 1, r, 2*n + 1);
tree[n] = max(tree[2*n], tree[2*n + 1]);
}
void upd(int x, int v, int l, int r, int n) {
if(x < l || r < x) return;
if(l == r) {
tree[n] = v;
return;
}
int m = (l + r)>>1;
upd(x, v, l, m, 2*n);
upd(x, v, m + 1, r, 2*n + 1);
tree[n] = max(tree[2*n], tree[2*n + 1]);
}
void upd(int x, int v) { upd(x, v, 0, Z - 1, 1); }
};
BIT bit[MN];
RMQ rmq[MN];
struct Info {
int v, i, j, l;
bool operator <(const Info &i) const {
return v < i.v;
}
};
priority_queue<Info> cand, pq;
vector<Info> P;
int la[MN];
void relax() {
while(!cand.empty()) {
Info t = cand.top();
int x = t.j;
if(t.l != la[x]) {
cand.pop();
continue;
}
break;
}
}
int main() {
std::ios::sync_with_stdio(false);
cin >> N;
for(int i = 0; i < N; i++) {
int a, b; cin >> a >> b;
V[--a].push_back(b);
}
for(int i = 0; i < N; i++) {
int c, d; cin >> c >> d;
X[--c].push_back(d);
}
int ans = 0;
for(int i = 0; i < N; i++) {
sort(V[i].begin(), V[i].end());
sort(X[i].begin(), X[i].end());
vector<int> chk(V[i].size(), 0);
vector<int> tmp;
int pos = (int)X[i].size() - 1;
for(int j = (int)V[i].size() - 1; j >= 0; j--) {
if(pos >= 0 && V[i][j] <= X[i][pos]) {
pos--;
continue;
}
freeV.push(V[i][j]);
chk[j] = 1;
}
for(int j = 0; j < V[i].size(); j++) if(!chk[j]) tmp.push_back(V[i][j]);
V[i] = tmp;
if(V[i].size() == 0) {
for(int j = 0; j < X[i].size(); j++) {
freeX.insert(X[i][j]);
}
la[i] = -1;
continue;
}
bit[i].init(V[i].size());
rmq[i].init(V[i].size());
chk = vector<int>(X[i].size(), 0);
pos = 0;
for(int j = 0; j < V[i].size(); j++) {
while(pos < X[i].size() && X[i][pos] < V[i][j]) pos++;
chk[pos] = 1;
pos++;
P.push_back({V[i][j], i, j});
}
tmp.clear();
for(int j = 0; j < X[i].size(); j++) {
if(chk[j]) tmp.push_back(X[i][j]);
else freeX.insert(X[i][j]);
}
X[i] = tmp;
pos = (int)X[i].size() - 1;
for(int j = (int)V[i].size() - 1; j >= 0; j--) {
while(pos >= 0 && X[i][pos] >= V[i][j]) pos--;
bit[i].upd(j, j, j - pos);
}
pii t = bit[i].tree[1];
pq.push({ X[i].back(), V[i][-t.second], i });
la[i] = (int)V[i].size() - 1;
}
ans += freeV.size();
sort(P.begin(), P.end());
int pos = (int)P.size() - 1;
while(!freeV.empty()) {
int v = freeV.top(); freeV.pop();
while(pos >= 0 && P[pos].v >= v) {
int x = P[pos].i;
if(P[pos].j != la[x]) {
pos--;
continue;
}
bit[x].upd(la[x], la[x], 1e9);
rmq[x].upd(la[x], -1);
la[x] = rmq[x].tree[1];
if(la[x] >= 0) {
pii t = bit[x].tree[1];
pq.push({ X[x][ la[x] ], V[x][-t.second], x, la[x] });
}
pos--;
}
while(!pq.empty() && pq.top().v >= v) {
Info t = pq.top(); pq.pop();
cand.push({ -t.i, t.v, t.j });
}
auto it = freeX.lower_bound(v);
if(it != freeX.end()) {
freeX.erase(it);
continue;
}
ans++;
relax();
Info t = cand.top(); cand.pop();
int x = t.j;
int s = lower_bound(V[x].begin(), V[x].end(), t.i) - V[x].begin();
int e = la[x];
bit[x].upd(s, e, -1);
bit[x].upd(s, s, 1e9);
bit[x].upd(e, e, 1e9);
rmq[x].upd(s, -1);
rmq[x].upd(e, -1);
la[x] = rmq[x].tree[1];
if(la[x] >= 0) {
pii t = bit[x].tree[1];
pq.push({ X[x][ la[x] ], V[x][-t.second], x, la[x] });
}
freeV.push(V[x][s]);
}
cout << ans;
}
Compilation message
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:161:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < V[i].size(); j++) if(!chk[j]) tmp.push_back(V[i][j]);
~~^~~~~~~~~~~~~
worst_reporter2.cpp:165:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < X[i].size(); j++) {
~~^~~~~~~~~~~~~
worst_reporter2.cpp:178:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < V[i].size(); j++) {
~~^~~~~~~~~~~~~
worst_reporter2.cpp:179:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(pos < X[i].size() && X[i][pos] < V[i][j]) pos++;
~~~~^~~~~~~~~~~~~
worst_reporter2.cpp:187:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < X[i].size(); j++) {
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
27000 KB |
Output is correct |
| 2 |
Execution timed out |
2059 ms |
26872 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
27000 KB |
Output is correct |
| 2 |
Execution timed out |
2059 ms |
26872 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
27000 KB |
Output is correct |
| 2 |
Execution timed out |
2059 ms |
26872 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
27000 KB |
Output is correct |
| 2 |
Execution timed out |
2059 ms |
26872 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
