玄学做法,其他地方AC,洛谷爆零
查看原帖
玄学做法,其他地方AC,洛谷爆零
119533
noctua楼主2021/10/24 20:25
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <memory.h>
using namespace std;

const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m1, m2;

struct plane {
    int l, r;
    int val;
};

plane a[MAXN];
plane b[MAXN];

int data[MAXN];

int nxt1[MAXN];
int sum2[MAXN];



bool cmp(plane x, plane y) {
    return x.l < y.l;
}


vector <plane> lsh;

int findnxt(int x, int l, int r) {
    if (x >= lsh[r].l || lsh[l].r > lsh[r].l) {
        //cout << "tgrre" << endl;
        return -1;
    }
    int mid = (l + r) >> 1;
    while (l < r) {
        mid = (l + r) >> 1;
        //cout << "mid: " << mid << endl;
        //cout << "l: " << l << " r: " << r << endl;
        //cout << "a[l]: " << lsh[l].l << " a[r]: " << lsh[r].l << " a[mid]: " << lsh[mid].l << endl << endl;
        if (lsh[mid].l < x) {
            l = mid + 1;
        }
        else {
            r = mid;
        }

        
    }

    return l;
}


int res[MAXN];
int res2[MAXN];

int main() {
    //freopen("airport.in", "r", stdin);
    //freopen("airport.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin >> n >> m1 >> m2;

    for (int i = 1; i <= m1; i++) {
        cin >> a[i].l >> a[i].r;
    }


    sort(a + 1, a + 1 + m1, cmp);
    

    for (int i = 1; i <= m1; i++) {
        lsh.push_back(a[i]);
    }
    
    int m1clone = m1;
    int m2clone = m2;
    
    int cnt = 1;
    int i = 0;
    
    while (lsh.size() > 0) {
        res[cnt]++;
        int tmpi = i;
        
        i = findnxt(lsh[i].r, i, lsh.size() - 1);
        if (i == -1) {
            i = 0;
            if (res[cnt] == 0) {
                break;
            }
            cnt++;
        }
        else {
            i--;
        }
        lsh.erase(lsh.begin() + tmpi);
        //cout << "i: " << i << endl;
    }
    res[0] = 0;
    for (int i = 1; i <= cnt; i++) {
        res[i] += res[i - 1];
    }


    lsh.clear();
    memset(a + 1, 0, sizeof(a));

    for (int i = 1; i <= m2; i++) {
        cin >> a[i].l >> a[i].r;
    }


    sort(a + 1, a + 1 + m2, cmp);
    

    for (int i = 1; i <= m2; i++) {
        lsh.push_back(a[i]);
    }
    

    m1clone = m2;
    
    cnt = 1;
    i = 0;
    
    while (lsh.size() > 0) {
        res2[cnt]++;
        int tmpi = i;
        
        i = findnxt(lsh[i].r, i, lsh.size() - 1);
        if (i == -1) {
            i = 0;
            cnt++;
        }
        else {
            i--;
        }
        lsh.erase(lsh.begin() + tmpi);
    }
    res2[0] = 0;
    for (int i = 1; i <= cnt; i++) {
        res2[i] += res2[i - 1];
    }

    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = max(ans, res[i] + res2[n - i]);
    }

    cout << ans << endl;
    return 0;
}
2021/10/24 20:25
加载中...