oj.uz

답안 #216049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
216049 2020-03-26T16:47:54 Z tatyam Pairs (IOI07_pairs) C++17
92 / 100
 1046 ms 175736 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define all(a) begin(a), end(a)
#define each(i,a) for(auto&& i : a)
#define overload3(_1, _2, _3, name, ...) name
#define rep1(n) for(int i = 0; i < (n); i++)
#define rep2(i, n) for(int i = 0; i < (n); i++)
#define rep3(i, a, b) for(int i = (a); i < (b); i++)
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
 

struct SegTree1{
    static constexpr int size = 225;
    int data[size * 2];
    void add(int x, int val){
        x += size;
        do{
            data[x] += val;
        }while(x /= 2);
    }
    int get(int x1, int x2){
        int ans = 0;
        for(; x1 < x2; x1 /= 2, x2 /= 2){
            if(x1 & 1) ans += data[x1++];
            if(x2 & 1) ans += data[--x2];
        }
        return ans;
    }
};
struct SegTree2{
    static constexpr int size = 225;
    SegTree1 data[size * 2];
    void add(int x, int y, int val){
        x += size;
        do{
            data[x].add(y, val);
        }while(x /= 2);
    }
    int get(int x1, int x2, int y1, int y2){
        int ans = 0;
        for(; x1 < x2; x1 /= 2, x2 /= 2){
            if(x1 & 1) ans += data[x1++].get(y1, y2);
            if(x2 & 1) ans += data[--x2].get(y1, y2);
        }
        return ans;
    }
};
struct SegTree3{
    static constexpr int size = 225;
    SegTree2 data[size * 2];
    void add(int x, int y, int z, int val){
        x += size;
        do{
            data[x].add(y, z, val);
        }while(x /= 2);
    }
    int get(int x1, int x2, int y1, int y2, int z1, int z2){
        chmax(x1, 0);
        chmin(x2, size);
        chmax(y1, 0);
        chmin(y2, size);
        chmax(z1, 0);
        chmin(z2, size);
        int ans = 0;
        x1 += size;
        x2 += size;
        y1 += size;
        y2 += size;
        z1 += size;
        z2 += size;
        for(; x1 < x2; x1 /= 2, x2 /= 2){
            if(x1 & 1) ans += data[x1++].get(y1, y2, z1, z2);
            if(x2 & 1) ans += data[--x2].get(y1, y2, z1, z2);
        }
        return ans;
    }
};
struct SegTree{
    static constexpr int size = 150000;
    int data[size * 2];
    void add(int x, int val){
        x += size;
        do{
            data[x] += val;
        }while(x /= 2);
    }
    int get(int x1, int x2){
        chmax(x1, 0);
        chmin(x2, size);
        int ans = 0;
        x1 += size;
        x2 += size;
        for(; x1 < x2; x1 /= 2, x2 /= 2){
            if(x1 & 1) ans += data[x1++];
            if(x2 & 1) ans += data[--x2];
        }
        return ans;
    }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int b, n, d, m;
    cin >> b >> n >> d >> m;
    ll ans = 0;
    if(b == 1){
        vector<int> a(n);
        each(i, a) cin >> i;
        sort(all(a));
        int min = 0;
        rep(n){
            while(a[i] - a[min] > d) min++;
            ans += i - min;
        }
    }
    else if(b == 2){
        vector<pii> a(n);
        each(i, a){
            cin >> i.first >> i.second;
            i.first--; i.second--;
        }
        each(i, a) i = {i.first + i.second, i.first - i.second + 74999};
        sort(all(a));
        SegTree seg;
        int min = 0;
        rep(n){
            while(a[i].first - a[min].first > d){
                seg.add(a[min].second, -1);
                min++;
            }
            ans += seg.get(a[i].second - d, a[i].second + d + 1);
            seg.add(a[i].second, 1);
        }
    }
    else{
        vector<array<int, 4>> a(n);
        each(i, a){
            cin >> i[0] >> i[1] >> i[2];
            i[0]--; i[1]--; i[2]--;
        }
        each(i, a) i = {i[0] + i[1] + i[2], -i[0] + i[1] + i[2] + 74, i[0] - i[1] + i[2] + 74, i[0] + i[1] - i[2] + 74};
        sort(all(a));
        static SegTree3 seg;
        int min = 0;
        rep(n){
            while(a[i][0] - a[min][0] > d){
                seg.add(a[min][1], a[min][2], a[min][3], -1);
                min++;
            }
            ans += seg.get(a[i][1] - d, a[i][1] + d + 1, a[i][2] - d, a[i][2] + d + 1, a[i][3] - d, a[i][3] + d + 1);
            seg.add(a[i][1], a[i][2], a[i][3], 1);
        }
    }
    cout << ans << endl;
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 1152 KB Output is correct
2 Correct 17 ms 1152 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 1664 KB Output is correct
2 Correct 25 ms 1664 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 1664 KB Output is correct
2 Correct 27 ms 1664 KB Output is correct
3 Correct 25 ms 1664 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 6 ms 1536 KB Output is correct

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 1784 KB Output is correct
2 Correct 32 ms 1784 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 1920 KB Output is correct
2 Correct 45 ms 1920 KB Output is correct
3 Correct 41 ms 1920 KB Output is correct
4 Correct 45 ms 1920 KB Output is correct

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 3448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 70264 KB Output is correct
2 Correct 42 ms 70400 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 8060 KB Output is correct
2 Correct 242 ms 8056 KB Output is correct
3 Correct 194 ms 8056 KB Output is correct

Subtask #12
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 700 ms 118156 KB Output is correct
2 Correct 800 ms 118216 KB Output is correct
3 Correct 487 ms 118136 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1046 ms 175660 KB Output is correct
2 Correct 1010 ms 175608 KB Output is correct
3 Correct 617 ms 175736 KB Output is correct