Submission #1201509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201509		adiyer	Pairs (IOI07_pairs)	C++20	100 / 100	3167 ms	3092 KiB

pairs

#pragma optimize ("g",on)
#pragma GCC optimize("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

const int N = 2e5 + 11;

ll B, n, k, m;
ll a[N], b[N], c[N], t[N];

long long res;

vector < pair < ll, ll > > scan;
vector < pair < ll, ll > > v[100];

void add(ll i, ll x){
    for(; i < N; i += (i & (-i))) t[i] += x;
}

ll get(ll r){
    ll ret = 0;
    for(; r > 0; r -= (r & (-r))) ret += t[r];
    return ret;
}

ll get(ll l, ll r){
    return get(r) - get(l - 1);
}

ll count(ll d){
    sort(scan.begin(), scan.end());
    ll j = 0, cur = 0;
    for(auto x : scan){
        while(x.first - scan[j].first > d) add(scan[j].second, -1), j++;
        cur += get(x.second - d, x.second + d), add(x.second, 1);
    }
    while(j < scan.size()) add(scan[j].second, -1), j++;
    return cur;
}

ll calc(ll i1, ll i2){
    ll d = k - abs(i1 - i2), cur = 0;
    if(v[i1].empty() || v[i2].empty() || d < 0) return 0;
    scan.clear();
    for(auto x : v[i1]) scan.push_back({x.first - x.second, x.first + x.second});
    for(auto x : v[i2]) scan.push_back({x.first - x.second, x.first + x.second});
    cur += count(d);
    scan.clear();
    for(auto x : v[i1]) scan.push_back({x.first - x.second, x.first + x.second});
    cur -= count(d);
    scan.clear();
    for(auto x : v[i2]) scan.push_back({x.first - x.second, x.first + x.second});
    cur -= count(d);
    return cur;
}

void solve(){
    cin >> B >> n >> k >> m;
    if(B == 3){
        for(ll i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i], v[a[i]].push_back({b[i], c[i]});
        for(ll i = 1; i <= m; i++) sort(v[i].begin(), v[i].end());
        for(ll i1 = 1; i1 <= m; i1++){
            for(ll i2 = 1; i2 <= m; i2++){
                res += calc(i1, i2);
            }
        }
        cout << (res - n) / 2;
    }
    else if(B == 1){
        for(ll i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + n + 1);
        for(ll i = 1; i <= n; i++){
            ll L, R, l, r;
            l = 0, r = n;
            while(r - l > 1){
                ll md = (l + r) / 2;
                if(a[md] + k >= a[i]) r = md;
                else l = md;
            }
            L = r;
            l = 0, r = n + 1;
            while(r - l > 1){
                ll md = (l + r) / 2;
                if(a[md] - k <= a[i]) l = md;
                else r = md;
            }
            R = l;
            res += (R - L + 1);
            // cout << i << ' ' << L << ' ' << R << '\n';
        }
        cout << (res - n) / 2;
    }
    else{
        vector < pair < ll, ll > > scan;
        for(ll i = 1; i <= n; i++) cin >> a[i] >> b[i];
        for(ll i = 1; i <= n; i++) scan.push_back({a[i] - b[i], a[i] + b[i]});
        sort(scan.begin(), scan.end());
        ll j = 0;
        for(auto x : scan){
            while(x.first - scan[j].first > k) add(scan[j].second, -1), j++;
            res += get(x.second - k, x.second + k), add(x.second, 1);
        }
        cout << res;
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
}

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10