oj.uz

Submission #54556

# Submission time Handle Problem Language Result Execution time Memory
54556 2018-07-04T05:26:14 Z 강태규(#1489) Pairs (IOI07_pairs) C++11
100 / 100
 415 ms 47484 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, d, m;

struct data1 {
    int x[100000];
};

llong solve1() {
    data1 &a = *(new data1());
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a.x[i]);
    }
    sort(a.x, a.x + n);
    llong ret = 0;
    for (int i = 0, j = 1; i < n; ++i) {
        while (j < n && a.x[j] - a.x[i] <= d) ++j;
        ret += j - i;
    }
    return ret - n;
}

struct data2 {
    int x[100000];
    int y[100000];
    pii ps[100000];
    int seg[150000] = {};
    int mx;
    
    void update(int i, int v) {
        while (i <= mx) {
            seg[i] += v;
            i += i & -i;
        }
    }
    
    int query(int i) {
        int ret = 0;
        while (i) {
            ret += seg[i];
            i -= i & -i;
        }
        return ret;
    }
};

llong solve2() {
    data2 &a = *(new data2());
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &a.x[i], &a.y[i]);
        a.ps[i] = pii(a.x[i] + a.y[i] - 1, a.x[i] - a.y[i] + m);
    }
    sort(a.ps, a.ps + n);
    a.mx = (m << 1) - 1;
    llong ret = 0;
    for (int i = 0, j = 0; i < n; ++i) {
        while (j < n && a.ps[j].first - a.ps[i].first <= d)
            a.update(a.ps[j++].second, 1);
        a.update(a.ps[i].second, -1);
        ret += a.query(min(a.ps[i].second + d, a.mx));
        ret -= a.query(max(a.ps[i].second - d - 1, 0));
    }
    return ret;
}

struct data3 {
    int x[100000];
    int y[100000];
    int z[100000];
    int mx;
    
    int seg[224][224][224] = {};
    
    struct point {
        int x, y, z, w;
        point() {}
        point(int x, int y, int z)
         : x(x + y + z - 2), y(x + y - z + m - 1),
          z(x - y + z + m - 1), w(x - y - z + 2 * m) {}
        bool operator<(const point &p) const {
            return w < p.w;
        }
    } ps[100000];
    
    void update(int _x, int _y, int _z, int v) {
        int x, y, z;
        x = _x;
        while (x <= mx) {
            y = _y;
            while (y <= mx) {
                z = _z;
                while (z <= mx) {
                    seg[x][y][z] += v;
                    z += z & -z;
                }
                y += y & -y;
            }
            x += x & -x;
        }
    }
    
    int in(int x) {
        return max(min(x, mx), 0);
    }
    
    int query(int _x, int _y, int _z) {
        int x, y, z, ret = 0;
        x = _x;
        while (x) {
            y = _y;
            while (y) {
                z = _z;
                while (z) {
                    ret += seg[x][y][z];
                    z -= z & -z;
                }
                y -= y & -y;
            }
            x -= x & -x;
        }
        return ret;
    }
};

llong solve3() {
    data3 &a = *(new data3());
    a.mx = m;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d%d", &a.x[i], &a.y[i], &a.z[i]);
        a.ps[i] = data3::point(a.x[i], a.y[i], a.z[i]);
    }
    sort(a.ps, a.ps + n);
    a.mx = 3 * m - 2;
    llong ret = 0;
    for (int i = 0, j = 0; i < n; ++i) {
        while (j < n && a.ps[j].w - a.ps[i].w <= d) 
            a.update(a.ps[j].x, a.ps[j].y, a.ps[j].z, 1), ++j;
        a.update(a.ps[i].x, a.ps[i].y, a.ps[i].z, -1);
        int x = a.ps[i].x;
        int y = a.ps[i].y;
        int z = a.ps[i].z;
        
        for (int i = 0; i <= 1; ++i) {
            int qx = x + (2 * i - 1) * d + (i - 1);
            for (int j = 0; j <= 1; ++j) {
                int qy = y + (2 * j - 1) * d + (j - 1);
                for (int k = 0; k <= 1; ++k) {
                    int qz = z + (k * 2 - 1) * d + (k - 1);
                    ret += ((((i ^ j ^ k) & 1) << 1) - 1)
                        * a.query(a.in(qx), a.in(qy), a.in(qz));
                }
            }
        }
    }
    return ret;
}

int main() {
    int b;
    scanf("%d%d%d%d", &b, &n, &d, &m);
    llong ans;
    if (b == 1) ans = solve1();
    else if (b == 2) ans = solve2();
    else ans = solve3();
    printf("%lld\n", ans);
	return 0;
}

Compilation message

pairs.cpp: In function 'llong solve1()':
pairs.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a.x[i]);
         ~~~~~^~~~~~~~~~~~~~~
pairs.cpp: In function 'llong solve2()':
pairs.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a.x[i], &a.y[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'llong solve3()':
pairs.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a.x[i], &a.y[i], &a.z[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:178:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &b, &n, &d, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 872 KB Output is correct
2 Correct 20 ms 1048 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1048 KB Output is correct
2 Correct 26 ms 1048 KB Output is correct
3 Correct 25 ms 1048 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

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

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2664 KB Output is correct
2 Correct 40 ms 2664 KB Output is correct
3 Correct 56 ms 2664 KB Output is correct
4 Correct 40 ms 2764 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2788 KB Output is correct
2 Correct 49 ms 2788 KB Output is correct
3 Correct 44 ms 2788 KB Output is correct
4 Correct 45 ms 2788 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47340 KB Output is correct
2 Correct 47 ms 47340 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 47340 KB Output is correct
2 Correct 104 ms 47352 KB Output is correct
3 Correct 93 ms 47468 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 47468 KB Output is correct
2 Correct 364 ms 47468 KB Output is correct
3 Correct 148 ms 47468 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 47468 KB Output is correct
2 Correct 369 ms 47484 KB Output is correct
3 Correct 275 ms 47484 KB Output is correct