Submission #783262

#	Time	Username	Problem	Language	Result	Execution time	Memory
783262		PanosPask	Pairs (IOI07_pairs)	C++14	60 / 100	62 ms	7356 KiB

pairs

#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 (stderr)

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 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10