RT,我的做法是 O(n2logn),为什么全部都是 WA+TLE
//SN-00129 ����� ������һ�з�У
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int N, n, m1, m2, L, R, sum, cnt1, cnt2, ans1[100001], ans2[100001];
struct plane1{
int l, r;
}a[100001];
bool cmp(plane1 a, plane1 b){
return a.l < b.l;
}
struct plane2{
int l, r;
bool operator < (const plane2 &x) const{
return r > x.r;
}
}dlr;
priority_queue <plane2> q1, q2;
void change1(int i){
dlr = q1.top();
if (a[i].l > dlr.r){
q1.pop();
dlr.l = a[i].l;
dlr.r = a[i].r;
cnt1++;
q1.push(dlr);
}else{
if (sum < n){
sum++;
dlr.l = a[i].l;
dlr.r = a[i].r;
cnt1++;
q1.push(dlr);
}
}
}
void update1(){
while (!q1.empty()) q1.pop();
sum = 0;
dlr.l = a[1].l;
dlr.r = a[1].r;
cnt1++;
sum++;
q1.push(dlr);
}
void change2(int i){
dlr = q2.top();
if (a[i].l > dlr.r){
q2.pop();
dlr.l = a[i].l;
dlr.r = a[i].r;
cnt2++;
q2.push(dlr);
}else{
if (sum < n){
sum++;
dlr.l = a[i].l;
dlr.r = a[i].r;
cnt2++;
q2.push(dlr);
}
}
}
void update2(){
while (!q2.empty()) q2.pop();
sum = 0;
dlr.l = a[1].l;
dlr.r = a[1].r;
cnt2++;
sum++;
q2.push(dlr);
}
int main(){
//freopen("airport.in", "r", stdin);
//freopen("airport.out", "w", stdout);
scanf("%d%d%d", &N, &m1, &m2);
for (int i = 1; i <= m1; i++){
scanf("%d%d", &a[i].l, &a[i].r);
}
sort(a + 1, a + 1 + m1, cmp);
for (n = 1; n <= N; n++){
cnt1 = 0;
update1();
for (int i = 2; i <= m1; i++){
change1(i);
}
ans1[n] = cnt1;
//printf("%d\n", cnt1);
}
for (int i = 1; i <= m2; i++){
scanf("%d%d", &a[i].l, &a[i].r);
}
sort(a + 1, a + 1 + m2, cmp);
for (n = 1; n <= N; n++){
cnt2 = 0;
update2();
for (int i = 2; i <= m1; i++){
change2(i);
}
ans2[n] = cnt2;
//printf("%d\n", cnt2);
}
int ans = -1;
for (int i = 0; i <= N; i++){
ans = max(ans, ans1[i] + ans2[N - i]);
//printf("%d %d\n", cnt1[i], cnt2[i - 1]);
}
printf("%d", ans);
return 0;
}
救救孩子吧,我还年轻,不想AFO