Submission #1141911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141911		farica	Pairs (IOI07_pairs)	C++20	100 / 100	278 ms	219372 KiB

pairs

#include <bits/stdc++.h>
#define int long long

using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
using ll = long long;

const int N = 2e5 + 5;

int m, d;
vi bit1d;

template<class T, int... Ns> struct BIT {
    T val = 0;
    void upd(T v) { val += v; }
    T query() { return val; }
};
template<class T, int N, int... Ns> struct BIT<T, N, Ns...> {
    BIT<T, Ns...> bit[N+1];
    template<typename... Args> void upd(int pos, Args... args) {
        for (; pos <= N; pos += pos&-pos) bit[pos].upd(args...);
    }
    template<typename... Args> T sum(int pos, Args... args) {
        T res = 0; for (; pos > 0; pos -= pos&-pos) res += bit[pos].query(args...);
        return res;
    }
    template<typename... Args> T query(int l, int r, Args... args) {
        return sum(r, args...) - sum(l-1, args...);
    }
};

void update1d(int x, int val) {
    for(; x <= 2*m+1; x += x & -x) bit1d[x] += val;
}

int query1d(int x) {
    if(x <= 0) return 0;
    int sum = 0;
    for(; x > 0; x -= x & -x) sum += bit1d[x];
    return sum;
}

int sum1d(int x, int y) {
    return query1d(y) - query1d(x-1);
}

void solve() {
   int b, n;
   cin >> b >> n >> d >> m;
   if(b == 1) {
        int a[n];
        for(int i=0; i<n; ++i) cin >> a[i];
        sort(a, a+n);
        int ans = 0, L = 0;
        for(int i=0; i<n; ++i) {
            while((a[i] - a[L]) > d) ++L;
            ans += i - L;
        }
        cout << ans << endl;
   } else if(b == 2) {
       bit1d.assign(2*m+2, 0);
       vector<pi>v(n);
       for(int i=0; i<n; ++i) {
        int x, y;
        cin >> x >> y;
        v[i] = {x+y, x-y+m+1};
       }
       sort(v.begin(), v.end());
       int ans = 0, L = 0;
       for(int i=0; i<n; ++i) {
            while((v[i].first - v[L].first) > d) {
                update1d(v[L].second, -1);
                ++L;
            }
            ans += sum1d(max(1LL,v[i].second - d), min(2*m+1, v[i].second + d));
            update1d(v[i].second, 1);
       }
       cout << ans << endl;
   } else {
       vector<array<int,4>>v(n);
       for(int i=0; i<n; ++i) {
            int x, y, z;
            cin >> x >> y >> z;
            v[i] = {x+y+z, x+y-z, x-y+z, x-y-z};
       }
       sort(v.begin(), v.end());
       BIT<int, 301, 301, 301> bit2;
       int L = 0, ans = 0;
       for(int i=0; i<n; ++i) {
            while((v[i][0] - v[L][0]) > d) {
                bit2.upd(v[L][1]+2*m+1, v[L][2]+2*m+1, v[L][3]+2*m+1, -1);
                ++L;
            }
            ans += bit2.query(max(1LL, v[i][1] + 2*m+1 - d), min(v[i][1] + 2*m+1 + d, 4*m+1),
                max(1LL, v[i][2] + 2*m+1 - d), min(v[i][2] + 2*m+1 + d, 4*m+1),
                max(1LL, v[i][3] + 2*m+1 - d), min(v[i][3] + 2*m+1 + d, 4*m+1));
            bit2.upd(v[i][1]+2*m+1, v[i][2]+2*m+1, v[i][3]+2*m+1, 1);
       }
       cout << ans << endl;
   }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1;
    while(t--) solve();

    return 0;
}

• 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