제출 #1307018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307018		nguyenkhangninh99	Pairs (IOI07_pairs)	C++20	100 / 100	163 ms	293928 KiB

pairs

#include <bits/stdc++.h>
using namespace std;

struct FenwickTree{
    vector<int> tree;
    void init(int n){
        tree.assign(n, 0);
    }
    void update(int p){     
        for(; p < tree.size(); p += p & -p) tree[p]++;
    }
    int get(int p){
        int res = 0;
        for(; p; p -= p & -p) res += tree[p];
        return res;
    }
} bit;
int range(int l, int r){
    return bit.get(r) - (l > 1 ? bit.get(l - 1) : 0);
}

namespace sub1{
    void solve(){
        int n, d, m; cin >> n >> d >> m;
        bit.init(m + 1);
        long long res = 0;
        for(int i = 1; i <= n; i++){
            int x; cin >> x;
            res += range(max(1, x - d), min(x + d, m));
            bit.update(x);
        }
        cout << res;
    }
};

namespace sub2{
    int range(int l, int r){
        return bit.get(r) - bit.get(l - 1);
    }
    void solve(){
        int n, d, m; cin >> n >> d >> m;
        vector<pair<int, int>> point(n + 1);
        for(int i = 1; i <= n; i++) cin >> point[i].first >> point[i].second;
        for(int i = 1; i <= n; i++) point[i] = {point[i].first + point[i].second, point[i].first - point[i].second + m};

        vector<vector<pair<int, int>>> del(2 * m + 67), add(2 * m + 67);
        vector<vector<int>> pos(2 * m + 67);
        bit.init(2 * m + 67);
        for(int i = 1; i <= n; i++){
            pos[point[i].first].push_back(point[i].second);
            int l = max(1, point[i].first - d), r = min(2 * m, point[i].first + d), u = max(1, point[i].second - d), v = min(2 * m, point[i].second + d);
            del[l - 1].push_back({u, v});
            add[r].push_back({u, v});
        }
        long long ans = 0;
        for(int i = 1; i <= 2 * m; i++){
            for(int j: pos[i]) bit.update(j);
            for(auto [l, r]: del[i]) ans -= range(l, r);
            for(auto [l, r]: add[i]) ans += range(l, r);
        }
        cout << (ans - n) / 2;
    }
};

namespace sub3{
    const int maxn = 85;
    int pre[2 * maxn][2 * maxn][2 * maxn];

    void solve(){
        int n, d, m; cin >> n >> d >> m;
        vector<array<int, 3>> point(n + 1);
        for(int i = 1; i <= n; i++) for(int j = 0; j <= 2; j++) cin >> point[i][j];

        for(int i = 1; i <= n; i++){
            pre[point[i][0]][point[i][1] + point[i][2]][point[i][1] + m - point[i][2]]++;
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= 2 * m; j++){
                for(int k = 1; k <= 2 * m; k++) pre[i][j][k] += pre[i][j - 1][k] + pre[i][j][k - 1] - pre[i][j - 1][k - 1];
            }
        }
        long long ans = 0;
        for(int i = 1; i <= n; i++){
            int x = point[i][0], y = point[i][1] + point[i][2], z = point[i][1] + m - point[i][2];
            for(int j = 1; j <= m; j++){
                if(abs(j - x) <= d){
                    int diff = d - abs(j - x);
                    int x1 = max(1, y - diff), x2 = min(m * 2, y + diff), y1 = max(1, z - diff), y2 = min(m * 2, z + diff);
                    ans += pre[j][x2][y2] - pre[j][x1 - 1][y2] - pre[j][x2][y1 - 1] + pre[j][x1 - 1][y1 - 1];
                }
            }
        }
        cout << (ans - n) / 2;
    }
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int b; cin >> b;
    if(b == 1) sub1::solve();
    if(b == 2) sub2::solve();
    if(b == 3) sub3::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