oj.uz

Submission #783262

# Submission time Handle Problem Language Result Execution time Memory
783262 2023-07-14T19:14:12 Z PanosPask Pairs (IOI07_pairs) C++14
60 / 100
 62 ms 7356 KB 
#include <bits/stdc++.h>
#define mp make_pair

using namespace std;

typedef long long ll;

typedef pair<int, int> pi;

struct BITree {
    int size;
    vector<int> tree;

    void update(int i, int v) {
        for (int x = i; x < size; x = x | (x + 1))
            tree[x] += v;
    }

    int get(int i) {
        int res = 0;
        for (int x = i; x >= 0; x = (x & (x + 1)) - 1)
            res += tree[x];
        return res;
    }
    int get(int l, int r) {
        return get(r) - get(l - 1);
    }

    void init(int n) {
        size = n;
        tree.resize(size);
    }
};

int B, N, D, M;
ll ans = 0;

void case1(void)
{
    vector<int> animals(N);
    for (int i = 0; i < N; i++)
        scanf("%d", &animals[i]);
    sort(animals.begin(), animals.end());

    int l = 0;
    for (int r = 0; r < N; r++) {
        while (l < N && animals[r] - animals[l] > D) {
            l++;
        }

        ans += r - l;
    }

    printf("%lld\n", ans);
}

void case2(void)
{
    BITree plane;
    plane.init(2 * M + 1);

    vector<pair<pi, pi>> queries;
    vector<pi> points;

    for (int i = 0; i < N; i++) {
        int x, y;
        scanf("%d %d", &x, &y);

        int x1 = x - D - y;
        int x2 = x + D - y;
        int y1 = x - D + y;
        y1 = max(y1, 0);
        int y2 = x + D + y;
        y2 = min(y2, 2 * M);
        int n_x = x - y;
        int n_y = x + y;

        points.push_back(mp(n_x, n_y));

        x1--;
        queries.push_back(mp(mp(x1, -1), mp(y1, y2)));
        queries.push_back(mp(mp(x2, +1), mp(y1, y2)));
    }

    sort(points.begin(), points.end());
    sort(queries.begin(), queries.end());

    int to_add = 0;
    for (auto q : queries) {
        while (to_add < N && points[to_add].first <= q.first.first) {
            plane.update(points[to_add].second, 1);
            to_add++;
        }

        ans += plane.get(q.second.first, q.second.second) * q.first.second;
    }

    ans = (ans - N) / 2;

    printf("%lld\n", ans);
}

void case3(void)
{
    printf("-1\n");
}

int main(void)
{
    scanf("%d %d %d %d", &B, &N, &D, &M);

    if (B == 1)
        case1();
    else if (B == 2)
        case2();
    else
        case3();

    return 0;
}

Compilation message

pairs.cpp: In function 'void case1()':
pairs.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d", &animals[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'void case2()':
pairs.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     scanf("%d %d %d %d", &B, &N, &D, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 696 KB Output is correct
2 Correct 11 ms 700 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 596 KB Output is correct
2 Correct 15 ms 596 KB Output is correct
3 Correct 14 ms 696 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 6440 KB Output is correct
2 Correct 40 ms 6468 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6652 KB Output is correct
2 Correct 55 ms 6724 KB Output is correct
3 Correct 57 ms 6680 KB Output is correct
4 Correct 50 ms 6500 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 7236 KB Output is correct
2 Correct 51 ms 7356 KB Output is correct
3 Correct 62 ms 7316 KB Output is correct
4 Correct 53 ms 7352 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -