C++ 代码

1. 空间复杂度高，自己想出来的不知道该如何进一步优化了
2. 实践复杂度$O(m)$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define x first
#define y second
const int N = 100010, M = 100000010;
typedef pair<int, int> PII; 
vector<PII> a;
int b1[N];  //记录当前大于等于y且为1的前缀和
int c0[N];  //记录当前小雨等于y且为0的前缀和
int res[N];  //记录正确的个数
int flag[M];  //标记当前等于y且已经统计的0的数的个数

int main() {
    int m;
    cin >> m;
    //exit(0);
    for (int i = 0; i < m; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        a.push_back({x, y});
    }
    sort(a.begin(), a.end());
    for (int i = 0, j = m - 1; i < m && j >= 0; i++, j--) {
        c0[i] += c0[i - 1];
        res[i] += c0[i] - flag[a[i].x];
        a[i].y == 0 && c0[i]++;
        a[i].y == 0 && flag[a[i].x]++;

        b1[j] += b1[j + 1];
        a[j].y == 1 && b1[j]++;
        res[j] += b1[j];
    }
    int maxn = 0, ans = 0;
    for (int i = 0; i < m; i++) {
        //printf("x = %d, y = %d\n", a[i].x, a[i].y);
        if (res[i] >= maxn) maxn = res[i], ans = a[i].x;
    }
    cout << ans << endl;
    return 0;
}