返回题解分享
讨论 / 题解分享/ 帖子详情

递增三元组(编程题) - 题解

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef pair<int,int> aII;  
using ll = long long;
using ULL = unsigned long long;
const int N = 1e5+5;

ll n;
int a[N], b[N], c[N];

int finds(int x) {
    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (a[mid] < x) l = mid;
        else r = mid - 1;
    }
    if (a[l] < x) return l;
    else return 0;
}

int findb(int x) {
    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (c[mid] > x) r = mid;
        else l = mid + 1;    
    }
    if (c[r] > x) return n - r + 1;
    else return 0;
}

inline void solve() { 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    sort(c+1,c+1+n);
    ll cnt = 0;
    for (int i = 1; i <= n; i++) {
        ll x = finds(b[i]);
        ll y = findb(b[i]);
        cnt += x * y; 
    }
    cout << cnt << endl;
}          

int main() { 
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1; 
    //int _; cin >> _;
    while (_--) solve();
    return 0;
}
0 回复 0 转发 0 喜欢 4 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!