oj.uz

Submission #160052

# Submission time Handle Problem Language Result Execution time Memory
160052 2019-10-25T19:06:57 Z karma Pairs (IOI07_pairs) C++14
100 / 100
 207 ms 9340 KB 
#include<bits/stdc++.h>
#define FileName      "test"
#define ll            long long
#define pb            emplace_back
#define fi            first
#define se            second
#define mp            make_pair

using namespace std;

typedef pair<int, int> pii;

struct OneD {
    int n, d, m; ll res = 0;
    void Solve() {
        cin >> n >> d >> m;
        vector<int> v(n);
        for(int& x: v) cin >> x;
        sort(v.begin(), v.end());
        for(int& x: v) res += upper_bound(v.begin(), v.end(), x + d) - lower_bound(v.begin(), v.end(), x - d);
        cout << (res - n) / 2;
    }
};

struct TwoD {
    #define N   75000
    #define M   (N << 1)
    int n, m, d, x, y, t[M];
    vector<pii> v;
    ll res;
    void Update(int x, int val) {for(; x < M; x += (x & -x)) t[x] += val;}
    int Get(int x) {int res = 0; for(; x > 0; x -= (x & -x)) res += t[x]; return res;}
    void Solve() {
        cin >> n >> d >> m; v.resize(n);
        memset(&t, 0, sizeof t);
        for(int i = 0; i < n; ++i) {
            cin >> x >> y;
            v[i].fi = x + y;
            v[i].se = x - y + N;
        }
        sort(v.begin(), v.end());
        int j = 0; res = 0;
        for(int i = 0; i < n; ++i) {
           while(v[i].fi - v[j].fi > d && j < i) Update(v[j].se, -1), ++j;
           res += Get(min(v[i].se + d, M - 1)) - Get(v[i].se - d - 1);
           Update(v[i].se, 1);
        }
        cout << res;
    }
    #undef N
    #undef M
};

int cnt[77][160][160];
struct ThrD {
    int D, xD;
    int x, y, z, n, m, d;
    vector<pair<pii, int>> v;
    int Get(int x, int y, int z, int p, int q) {
        x = min(max(x, 1), 75);
        y = min(max(y, 1), 150);
        z = min(max(z, 1), 150);
        p = min(max(p, 1), 150);
        q = min(max(q, 1), 150);
        return cnt[x][p][q] + cnt[x][y - 1][z - 1] - cnt[x][p][z - 1] - cnt[x][y - 1][q];
    }
    void Solve() {
        cin >> n >> d >> m; v.resize(n);
        memset(&cnt, 0, sizeof cnt);
        for(int i = 0; i < n; ++i) {
            cin >> x >> y >> z;
            v[i] = mp(mp(x, y + z), y - z + 75);
            ++cnt[x][y + z][y - z + 75];
        }
        for(int i = 1; i <= 75; ++i) {
            for(int j = 1; j <= 150; ++j) {
                for(int k = 1; k <= 150; ++k)
                    cnt[i][j][k] += cnt[i][j][k - 1] + cnt[i][j - 1][k] - cnt[i][j - 1][k - 1];
            }
        }
        ll res = 0;
        for(int i = 0; i < n; ++i) {
            res += Get(v[i].fi.fi, v[i].fi.se - d, v[i].se - d, v[i].fi.se + d, v[i].se + d);
            for(int j = 1; j <= min(d, 75); ++j) {
                D = d - j;
                if(v[i].fi.fi - j > 0) res += Get(v[i].fi.fi - j, v[i].fi.se - D, v[i].se - D, v[i].fi.se + D, v[i].se + D);
                if(v[i].fi.fi + j <= m) res += Get(v[i].fi.fi + j, v[i].fi.se - D, v[i].se - D, v[i].fi.se + D, v[i].se + D);
            }
        }
        cout << (res - n) / 2;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(FileName".inp", "r")) {
       freopen(FileName".inp", "r", stdin);
       freopen(FileName".out", "w", stdout);
    }
    int B; cin >> B;
    if(B == 1) {
        OneD one;
        one.Solve();
    } else if(B == 2) {
        TwoD two;
        two.Solve();
    } else {
        ThrD thr;
        thr.Solve();
    }
}

Compilation message

pairs.cpp: In function 'int main()':
pairs.cpp:98:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".inp", "r", stdin);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:99:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".out", "w", stdout);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 760 KB Output is correct
2 Correct 22 ms 760 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 760 KB Output is correct
2 Correct 28 ms 760 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 760 KB Output is correct
2 Correct 31 ms 760 KB Output is correct
3 Correct 29 ms 760 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 3 ms 888 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1784 KB Output is correct
2 Correct 35 ms 1784 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1656 KB Output is correct
2 Correct 39 ms 1656 KB Output is correct
3 Correct 39 ms 1660 KB Output is correct
4 Correct 38 ms 1784 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1784 KB Output is correct
2 Correct 44 ms 1704 KB Output is correct
3 Correct 43 ms 1784 KB Output is correct
4 Correct 43 ms 1784 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8056 KB Output is correct
2 Correct 15 ms 8056 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9208 KB Output is correct
2 Correct 45 ms 9208 KB Output is correct
3 Correct 49 ms 9272 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9340 KB Output is correct
2 Correct 149 ms 9208 KB Output is correct
3 Correct 134 ms 9208 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 9204 KB Output is correct
2 Correct 207 ms 9208 KB Output is correct
3 Correct 162 ms 9208 KB Output is correct