Submission #1201457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201457		adiyer	Pairs (IOI07_pairs)	C++20	60 / 100	1202 ms	2752 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 < ll > v[100][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);
}

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]][b[i]].push_back(c[i]);
        for(ll i = 1; i <= m; i++)
            for(ll j = 1; j <= m; j++)
                sort(v[i][j].begin(), v[i][j].end());
        for(ll i1 = 1; i1 <= m; i1++){
            for(ll j1 = 1; j1 <= m; j1++){
                for(ll i2 = 1; i2 <= m; i2++){
                    for(ll j2 = 1; j2 <= m; j2++){
                        if(v[i2][j2].empty() || v[i1][j1].empty()) continue;
                        ll d = k - abs(i1 - i2) - abs(j1 - j2);
                        if(d < 0) continue;
                        // cout << d << ' ' << i1 << ' ' << j1 << ' ' << i2 << ' ' << j2 << '\n';
                        ll L = 0, R = v[i2][j2].size() - 1;
                        for(ll i = 0; i < v[i1][j1].size(); i++){
                            while(v[i2][j2][L] < v[i1][j1][i] - d) L++;
                            while(v[i2][j2][R] > v[i1][j1][i] + d) R--;
                            if(i1 == i2 && j1 == j2) R--;
                            res += (R - L + 1);
                            // cout << v[i1][j1][i] << ' ' << R - L + 1 << '\n';
                        }
                    }
                }
            }
        }
        cout << res;
    }
    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: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10