제출 #1287688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287688		canhnam357	Pairs (IOI07_pairs)	C++20	80 / 100	4105 ms	290624 KiB

pairs

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
void solve1() {
    int n, d, m;
    cin >> n >> d >> m;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    sort(all(a));
    long long ans = 0;
    for (int l = 0, r = 0; r < n; r++) {
        while (a[r] - a[l] > d) l++;
        ans += r - l;
    }
    cout << ans;
}
struct FakeFenwick { 
        vector<vector<int>> fw, val; 
        int n;
        FakeFenwick() {}
        FakeFenwick(int n): n(n), val(n + 1, vector<int>()), fw(n + 1) {} 
        bool iscc = 0; 
        void fakeU(int x, int y) { 
                iscc = 0; 
                for (; x <= n; x += x & -x) val[x].push_back(y); 
        }
        void cc() { 
                if (iscc) return; 
                for (int x = 1; x <= n; x++) { 
                        sort(all(val[x])); 
                        val[x].erase(unique(all(val[x])), val[x].end()); 
                        fw[x].resize(val[x].size() + 1); 
                }
                iscc = 1; 
        }
        void update(int x, int y, int v) { 
                assert(iscc); 
                for (; x <= n; x += x & -x) { 
                        int yy = upper_bound(all(val[x]), y) - val[x].begin(); 
                        for (; yy <= val[x].size(); yy += yy & -yy) { 
                                fw[x][yy] += v; 
                        }
                         
                }
        }
        int get(int x, int y) { 
                assert(iscc); 
                int res = 0; 
                for (; x; x -= x & -x) { 
                        int yy = upper_bound(all(val[x]), y) - val[x].begin(); 
                        for (; yy; yy -= yy & -yy) { 
                                res += fw[x][yy]; 
                        }
                }
                return res; 
        }
        int get(int x1, int y1, int x2, int y2)
        {
            return get(x2, y2) - get(x2, y1 - 1) - get(x1 - 1, y2) + get(x1 - 1, y1 - 1);
        }
};
void solve2() {
    // xi - xj + |yi - yj| <= d
    // xi + yi <= d + xj + yj if yi >= yj
    // xi - yi <= d + xj - yj if yi <  yj
    int n, m, d;
    cin >> n >> d >> m;
    vector<pair<int, int>> a(n);
    for (auto &[x, y] : a) cin >> x >> y;
    sort(all(a));
    FakeFenwick t1(m), t2(m);
    for (auto [x, y] : a) {
        t1.fakeU(y, d + x + y);
        t2.fakeU(y, d + x - y);
    }
    t1.cc();
    t2.cc();
    long long ans = 0;
    for (auto [x, y] : a) {
        ans += t1.get(1, x + y, y, d + m + m) + t2.get(y + 1, x - y, m, d + m + m);
        t1.update(y, d + x + y, 1);
        t2.update(y, d + x - y, 1);
    }
    cout << ans;
}
void solve3() {
    int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> a[75];
    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x--;
        a[x].emplace_back(y, z);
    }
    long long ans = 0;
    for (int i = 0; i < m; i++) {
        if (a[i].empty()) continue;
        sort(all(a[i]));
        FakeFenwick t1(m), t2(m);
        for (auto [x, y] : a[i]) {
            t1.fakeU(y, d + x + y);
            t2.fakeU(y, d + x - y);
        }
        t1.cc();
        t2.cc();
        for (auto [x, y] : a[i]) {
            ans += t1.get(1, x + y, y, d + m + m) + t2.get(y + 1, x - y, m, d + m + m);
            t1.update(y, d + x + y, 1);
            t2.update(y, d + x - y, 1);
        }
    }
    FakeFenwick t1[75], t2[75];
    for (int i = 0; i < m; i++) {
        if (a[i].empty()) continue;
        t1[i] = FakeFenwick(m);
        t2[i] = FakeFenwick(m);
        for (auto [x, y] : a[i]) {
            for (int z = 0; z < m; z++) {
                t1[i].fakeU(y, d - z + x + y);
                t2[i].fakeU(y, d - z + x - y);
            }
        }
        t1[i].cc();
        t2[i].cc();
    }
    for (int i = 0; i < m; i++) {
        if (a[i].empty()) continue;
        for (int j = i + 1; j < m; j++) {
            if (a[j].empty()) continue;
            int nd = d - (j - i);
            if (nd < 0) continue;
            swap(d, nd);
            int l = 0, r = 0;
            while (l < a[i].size() || r < a[j].size()) {
                if (l == a[i].size()) {
                    auto [x, y] = a[j][r++];
                    ans += t1[i].get(1, x + y, y, d + m + m) + t2[i].get(y + 1, x - y, m, d + m + m);
                    t1[j].update(y, d + x + y, 1);
                    t2[j].update(y, d + x - y, 1);
                }
                else if (r == a[j].size()) {
                    auto [x, y] = a[i][l++];
                    ans += t1[j].get(1, x + y, y, d + m + m) + t2[j].get(y + 1, x - y, m, d + m + m);
                    t1[i].update(y, d + x + y, 1);
                    t2[i].update(y, d + x - y, 1);
                }
                else if (a[j][r].first <= a[i][l].first) {
                    auto [x, y] = a[j][r++];
                    ans += t1[i].get(1, x + y, y, d + m + m) + t2[i].get(y + 1, x - y, m, d + m + m);
                    t1[j].update(y, d + x + y, 1);
                    t2[j].update(y, d + x - y, 1);
                }
                else {
                    auto [x, y] = a[i][l++];
                    ans += t1[j].get(1, x + y, y, d + m + m) + t2[j].get(y + 1, x - y, m, d + m + m);
                    t1[i].update(y, d + x + y, 1);
                    t2[i].update(y, d + x - y, 1);
                }
            }
            for (auto [x, y] : a[i]) {
                t1[i].update(y, d + x + y, -1);
                t2[i].update(y, d + x - y, -1);
            }
            for (auto [x, y] : a[j]) {
                t1[j].update(y, d + x + y, -1);
                t2[j].update(y, d + x - y, -1);
            }
            swap(d, nd);
        }
    }
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int type;
    cin >> type;
    if (type == 1) solve1();
    else if (type == 2) solve2();
    else solve3();   
    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: 0 / 10
• Subtask 13: 0 / 10