제출 #1307012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307012		nguyenkhangninh99	Pairs (IOI07_pairs)	C++20	70 / 100	156 ms	293784 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;

namespace sub1{
    int range(int l, int r){
        return bit.get(r) - (l > 1 ? bit.get(l - 1) : 0);
    }
    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) - (l > 1 ? bit.get(l - 1) : 0);
    }
    void solve(){
        int n, d, m; cin >> n >> d >> m;
        vector<pair<int, int>> point(n + 1);
        bit1.init(m + 1);
        bit2.init(m + 1);
        for(int i = 1; i <= n; i++) cin >> point[i].first >> point[i].second;
        sort(point.begin(), point.end());

        for(int i = 1; i <= n; i++){

        }
        cout << res;
    }
};*/

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