#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 la[MN];
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;
}
chk = vector<int>(X[i].size(), 0);
int pos1 = 0;
int pos2 = 0;
for(int j = 0; j < V[i].size(); j++) {
while(pos1 < X[i].size() && X[i][pos1] < V[i][j]) pos1++;
while(pos2 < X[i].size() && X[i][pos2] < V[i][j]) pos2++;
chk[pos2] = 1;
pos2++;
}
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;
la[i] = (int)V[i].size() - 1;
}
ans += freeV.size();
while(!freeV.empty()) {
int v = freeV.top(); freeV.pop();
auto it = freeX.lower_bound(v);
if(it != freeX.end()) {
freeX.erase(it);
continue;
}
ans++;
int mn = 1e9;
int p = -1;
for(int i = 0; i < N; i++) {
while(la[i] >= 0 && V[i][ la[i] ] <= v) la[i]--;
if(la[i] >= 0 && X[i][ la[i] ] >= v) {
int tmp = 1e9;
for(int j = la[i]; j >= 0; j--) {
if(j == 0 || X[i][j - 1] < V[i][j]) {
tmp = V[i][j];
break;
}
}
if(mn > tmp) {
mn = tmp;
p = i;
}
}
}
if(p == -1) {
while(1);
}
for(int i = la[p]; i >= 0; i--) {
if(i == 0 || X[p][i - 1] < V[p][i]) {
freeV.push(V[p][i]);
V[p][i] = v;
break;
}
else swap(v, V[p][i]);
}
}
cout << ans;
}
Compilation message
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:45: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:49:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < X[i].size(); j++) {
~~^~~~~~~~~~~~~
worst_reporter2.cpp:60:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < V[i].size(); j++) {
~~^~~~~~~~~~~~~
worst_reporter2.cpp:61:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(pos1 < X[i].size() && X[i][pos1] < V[i][j]) pos1++;
~~~~~^~~~~~~~~~~~~
worst_reporter2.cpp:62:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(pos2 < X[i].size() && X[i][pos2] < V[i][j]) pos2++;
~~~~~^~~~~~~~~~~~~
worst_reporter2.cpp:68: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 |
Execution timed out |
2058 ms |
9720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2058 ms |
9720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2058 ms |
9720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2058 ms |
9720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
