Submission #1201429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201429		adiyer	Pairs (IOI07_pairs)	C++20	50 / 100	4096 ms	4468 KiB

pairs

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 11;

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

vector < ll > v[100][100];

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++){
                        ll d = k - abs(i1 - i2) - abs(j1 - j2);
                        if(d < 0) continue;
                        for(ll i = 0; i < v[i1][j1].size(); i++){
                            if(v[i2][j2].empty()) continue;
                            ll L, R, l, r;
                            l = -1, r = v[i2][j2].size();
                            while(r - l > 1){
                                ll md = (l + r) / 2;
                                if(v[i2][j2][md] + d >= v[i1][j1][i]) r = md;
                                else l = md;
                            }
                            L = r + 1;
                            l = -1, r = v[i2][j2].size();
                            while(r - l > 1){
                                ll md = (l + r) / 2;
                                if(v[i2][j2][md] - d <= v[i1][j1][i]) l = md;
                                else r = md;
                            }
                            R = l + 1;
                            res += (R - L + 1);
                            // cout << d << ' ' << i1 << ' ' << j1 << ' ' << v[i1][j1][i] << ' ' << i2 << ' ' << j2 << ' ' << (R - L + 1) << '\n';
                        }
                    }
                }
            }
        }
        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;
    }
}

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: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10